Documentation

Crn.ExactMajorityStatic

Static exact majority with ties (CRN-5, [GHMSS16, Section 2]) #

The protocol P₁ of [GHMSS16, Section 2] (the majority protocol of [AADFP06], reporting ties). Every agent has a colour in {-1, 0, 1} (SignType); the protocol decides the sign of the sum of the colours, i.e. whether there are more 1s than -1s, fewer, or as many. The six states are the strong states [x] and the weak states ⟨x⟩, x ∈ {-1, 0, 1}, with weight w([x]) = x, w(⟨x⟩) = 0 (Fig. 1). Transitions (Fig. 2): [1] and [-1] annihilate into [0], [0]; a strong [x] turns a weak state into ⟨x⟩, and a strong [x], x ≠ 0, turns [0] into ⟨x⟩; other encounters change nothing. The table of Fig. 2 agrees with these rules (checked exhaustively).

Main statements:

The six states of the static majority protocol [GHMSS16, Fig. 1]: strong [x] and weak ⟨x⟩ for x ∈ {-1, 0, 1}.

Instances For

    The weight [GHMSS16, Fig. 1]: w([x]) = x, w(⟨x⟩) = 0.

    Equations
    Instances For

      The output (the reported sign of the colour sum): x in [x] and in ⟨x⟩.

      Equations
      Instances For

        The new state of an agent in state a meeting an agent in state b, outside annihilations [GHMSS16, Section 2]: a weak state meeting [y] becomes ⟨y⟩; [0] meeting [y], y ≠ 0, becomes ⟨y⟩; otherwise nothing changes.

        Equations
        Instances For

          The static majority protocol P₁ [GHMSS16, Section 2]: input colour x ↦ [x]. Its Bool output (more 1s than -1s) is not used; the outputs are StaticState.out.

          Equations
          Instances For

            Transitions preserve the total weight of the two agents [GHMSS16, proof of Lemma 1].

            R = ∑ |w| does not increase in an encounter [GHMSS16, proof of Lemma 2].

            Only [-1] has a negative weight.

            All states but [1] have a nonpositive weight.

            An encounter never removes the last strong state.

            theorem Crn.StaticState.δ_out (s : SignType) (a b : StaticState) (ha : a.out = s) (hb : b.out = s) :
            (δ (a, b)).1.out = s ∧ (δ (a, b)).2.out = s

            The states reporting s are closed under encounters.

            theorem Crn.StaticState.δ_recruit (s : SignType) (b : StaticState) (hb : b.weight = 0 ∨ b.weight = ↑s) (hs : b.out ≠ s) :

            [s] recruits every state of weight 0 or s that does not report s into ⟨s⟩.

            s · w ≤ |w| for a sign s.

            theorem Crn.StaticState.weight_eq_of_abs {s : SignType} {a : StaticState} (h : |a.weight| = ↑s * a.weight) :
            a.weight = 0 ∨ a.weight = ↑s

            |w| = s · w for a sign s forces w ∈ {0, s}.

            theorem Crn.StaticState.eq_strong_zero {a : StaticState} (h : a.isStrong = true) (h0 : a.weight = 0) :
            a = strong 0

            The only strong state of weight 0 is [0].

            theorem Crn.StaticState.eq_strong_of_weight {s : SignType} {a : StaticState} (h : a.weight = ↑s) (hs : s ≠ 0) :
            a = strong s

            The only state of weight s ≠ 0 is [s].

            theorem Crn.StaticState.weight_sum_eq {n : ℕ} {ι : Fin n → SignType} {c : Fin n → StaticState} (h : staticMajority.Reaches (staticMajority.input ∘ ι) c) :
            ∑ v : Fin n, (c v).weight = ∑ v : Fin n, ↑(ι v)

            [GHMSS16, Lemma 1] (Invariant 1). Along every execution, the sum of the weights equals the sum of the input colours.

            theorem Crn.StaticState.absWeight_sum_step_le {n : ℕ} {c d : Fin n → StaticState} (h : staticMajority.Step c d) :
            ∑ v : Fin n, |(d v).weight| ≤ ∑ v : Fin n, |(c v).weight|

            [GHMSS16, Lemma 2], first part (Invariant 2). R = ∑ |w| does not increase along a step.

            theorem Crn.StaticState.exists_reaches_absWeight_sum_eq {n : ℕ} {ι : Fin n → SignType} {c : Fin n → StaticState} (h : staticMajority.Reaches (staticMajority.input ∘ ι) c) :
            ∃ (d : Fin n → StaticState), staticMajority.Reaches c d ∧ ∑ v : Fin n, |(d v).weight| = |∑ v : Fin n, ↑(ι v)|

            [GHMSS16, Lemma 2], second part. From every reachable configuration, a configuration with R = |S| is reachable, S the sum of the input colours.

            theorem Crn.sum_signType_eq_counts {n : ℕ} (ι : Fin n → SignType) :
            ∑ v : Fin n, ↑(ι v) = ↑(↑(counts ι) 1) - ↑(↑(counts ι) (-1))

            The colour sum is #1 - #(-1).

            [GHMSS16, Theorem 3] The static majority protocol stably computes the sign of #1 - #(-1): all agents eventually and forever output 1 if there are more 1s than -1s, -1 if fewer, and 0 (a tie) if as many.