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:
StaticState.weight_sum_eq(Lemma 1): the weight sum equals the colour sum.StaticState.absWeight_sum_step_le,StaticState.exists_reaches_absWeight_sum_eq(Lemma 2):R = ∑ |w|does not increase and can be brought down to|∑ colours|.staticMajority_stablyComputes(Theorem 3): the protocol stably computes the sign of#1 - #(-1).
The six states of the static majority protocol [GHMSS16, Fig. 1]: strong [x] and weak
⟨x⟩ for x ∈ {-1, 0, 1}.
- strong
(x : SignType)
: StaticState
The strong state
[x]. - weak
(x : SignType)
: StaticState
The weak state
⟨x⟩.
Instances For
Equations
- Crn.instDecidableEqStaticState.decEq (Crn.StaticState.strong a) (Crn.StaticState.strong b) = if h : a = b then h ▸ isTrue ⋯ else isFalse ⋯
- Crn.instDecidableEqStaticState.decEq (Crn.StaticState.strong x_2) (Crn.StaticState.weak x_3) = isFalse ⋯
- Crn.instDecidableEqStaticState.decEq (Crn.StaticState.weak x_2) (Crn.StaticState.strong x_3) = isFalse ⋯
- Crn.instDecidableEqStaticState.decEq (Crn.StaticState.weak a) (Crn.StaticState.weak b) = if h : a = b then h ▸ isTrue ⋯ else isFalse ⋯
Instances For
The weight [GHMSS16, Fig. 1]: w([x]) = x, w(⟨x⟩) = 0.
Equations
- (Crn.StaticState.strong a).weight = ↑a
- (Crn.StaticState.weak a).weight = 0
Instances For
The output (the reported sign of the colour sum): x in [x] and in ⟨x⟩.
Equations
- (Crn.StaticState.strong a).out = a
- (Crn.StaticState.weak a).out = a
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
- (Crn.StaticState.weak x_2).recruit (Crn.StaticState.strong y) = Crn.StaticState.weak y
- (Crn.StaticState.strong SignType.zero).recruit (Crn.StaticState.strong y) = if y = 0 then Crn.StaticState.strong 0 else Crn.StaticState.weak y
- x✝¹.recruit x✝ = x✝¹
Instances For
The transition function of [GHMSS16, Fig. 2]: [1] and [-1] annihilate into [0], [0],
all other encounters recruit (recruit).
Equations
- Crn.StaticState.δ (Crn.StaticState.strong SignType.pos, Crn.StaticState.strong SignType.neg) = (Crn.StaticState.strong 0, Crn.StaticState.strong 0)
- Crn.StaticState.δ (Crn.StaticState.strong SignType.neg, Crn.StaticState.strong SignType.pos) = (Crn.StaticState.strong 0, Crn.StaticState.strong 0)
- Crn.StaticState.δ (a, b) = (a.recruit b, b.recruit a)
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
- Crn.staticMajority = { input := Crn.StaticState.strong, output := fun (s : Crn.StaticState) => decide (s.out = 1), δ := Crn.StaticState.δ }
Instances For
Strong states.
Equations
Instances For
Only [-1] has a negative weight.
All states but [1] have a nonpositive weight.
s · w ≤ |w| for a sign s.
The only strong state of weight 0 is [0].
The only state of weight s ≠ 0 is [s].
[GHMSS16, Lemma 1] (Invariant 1). Along every execution, the sum of the weights equals the sum of the input colours.
[GHMSS16, Lemma 2], second part. From every reachable configuration, a configuration with
R = |S| is reachable, S the sum of the input colours.
[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.