Dynamic exact majority with ties (CRN-5, [GHMSS16, Section 3]) #
The protocol P₂ of [GHMSS16, Section 3]. Every agent a carries a colour c_a ∈ {-1, 0, 1},
which an external force may change, and a state among the strong states [-2], …, [2] and the
weak states ⟨-1⟩, ⟨0⟩, ⟨1⟩, with weight w([z]) = z, w(⟨x⟩) = 0 (Fig. 3). Interactions
(the rules of the text of Section 3): [1], [-1] and [2], [-2] annihilate into [0], [0];
[2], [-1] become [1], [0] and [-2], [1] become [-1], [0]; a strong state of positive
(negative) weight turns weak states and [0] into ⟨1⟩ (⟨-1⟩); [0] turns weak states into
⟨0⟩. The interaction table does not read the colours. When the force changes c_a to
c_a + Δ, the state becomes [w(s_a) + Δ] (DynState.recolour, Fig. 3).
The colours are therefore kept outside the protocol: a configuration of P₂ is c : Fin n → DynState, and the colours col : Fin n → SignType are linked to it by the two invariants of
Section 3 (DynInv). For the relative majority protocol of Section 5, P₂ runs separately in
groups of agents (agents with the same label prefix); GStep grp is a step between two agents of
the same group, and DynInv grp holds group by group. With one group, GStep is Step.
Main statements:
DynInv.gstep,DynInv.recolour(Lemma 4): the invariants are preserved by interactions and by the external force.DynState.absWeight_sum_gstep_le(Lemma 5, first part),DynState.exists_greaches_noOpposite(Lemma 5, second part).DynInv.exists_stable(the conclusion of Section 3): from every configuration satisfying the invariants, interactions alone reach a configuration from which every agent forever outputs the sign of the colour sum of its group.dynamicMajority_stabilizes(Section 3 in protocol form): after any finite sequence of interactions and colour changes, the protocol stabilizes on the sign of the final colour sum.dynamicMajority_stablyComputes: without the force,P₂stably computes the sign of#1 - #(-1).
The table of Fig. 4 differs from the text in five entries. Four are harmless ([±2] meeting
[∓1] gives ⟨±1⟩ instead of [0], of the same weight). The entry for [1] meeting [0],
(⟨1⟩, [1]), needs a minor correction: it moves the weight to the [0] agent and breaks
Invariant 2 (an agent of colour -1 in state [0] would get [1], and a later change of its
colour to 1 would require the state [3]); the text's ([1], ⟨1⟩) is used.
Equations
- Crn.instDecidableEqDynState.decEq Crn.DynState.neg2 Crn.DynState.neg2 = isTrue ⋯
- Crn.instDecidableEqDynState.decEq Crn.DynState.neg2 Crn.DynState.neg1 = isFalse Crn.instDecidableEqDynState.decEq._proof_1
- Crn.instDecidableEqDynState.decEq Crn.DynState.neg2 Crn.DynState.zero = isFalse Crn.instDecidableEqDynState.decEq._proof_2
- Crn.instDecidableEqDynState.decEq Crn.DynState.neg2 Crn.DynState.pos1 = isFalse Crn.instDecidableEqDynState.decEq._proof_3
- Crn.instDecidableEqDynState.decEq Crn.DynState.neg2 Crn.DynState.pos2 = isFalse Crn.instDecidableEqDynState.decEq._proof_4
- Crn.instDecidableEqDynState.decEq Crn.DynState.neg2 (Crn.DynState.weak x_2) = isFalse ⋯
- Crn.instDecidableEqDynState.decEq Crn.DynState.neg1 Crn.DynState.neg2 = isFalse Crn.instDecidableEqDynState.decEq._proof_6
- Crn.instDecidableEqDynState.decEq Crn.DynState.neg1 Crn.DynState.neg1 = isTrue ⋯
- Crn.instDecidableEqDynState.decEq Crn.DynState.neg1 Crn.DynState.zero = isFalse Crn.instDecidableEqDynState.decEq._proof_7
- Crn.instDecidableEqDynState.decEq Crn.DynState.neg1 Crn.DynState.pos1 = isFalse Crn.instDecidableEqDynState.decEq._proof_8
- Crn.instDecidableEqDynState.decEq Crn.DynState.neg1 Crn.DynState.pos2 = isFalse Crn.instDecidableEqDynState.decEq._proof_9
- Crn.instDecidableEqDynState.decEq Crn.DynState.neg1 (Crn.DynState.weak x_2) = isFalse ⋯
- Crn.instDecidableEqDynState.decEq Crn.DynState.zero Crn.DynState.neg2 = isFalse Crn.instDecidableEqDynState.decEq._proof_11
- Crn.instDecidableEqDynState.decEq Crn.DynState.zero Crn.DynState.neg1 = isFalse Crn.instDecidableEqDynState.decEq._proof_12
- Crn.instDecidableEqDynState.decEq Crn.DynState.zero Crn.DynState.zero = isTrue ⋯
- Crn.instDecidableEqDynState.decEq Crn.DynState.zero Crn.DynState.pos1 = isFalse Crn.instDecidableEqDynState.decEq._proof_13
- Crn.instDecidableEqDynState.decEq Crn.DynState.zero Crn.DynState.pos2 = isFalse Crn.instDecidableEqDynState.decEq._proof_14
- Crn.instDecidableEqDynState.decEq Crn.DynState.zero (Crn.DynState.weak x_2) = isFalse ⋯
- Crn.instDecidableEqDynState.decEq Crn.DynState.pos1 Crn.DynState.neg2 = isFalse Crn.instDecidableEqDynState.decEq._proof_16
- Crn.instDecidableEqDynState.decEq Crn.DynState.pos1 Crn.DynState.neg1 = isFalse Crn.instDecidableEqDynState.decEq._proof_17
- Crn.instDecidableEqDynState.decEq Crn.DynState.pos1 Crn.DynState.zero = isFalse Crn.instDecidableEqDynState.decEq._proof_18
- Crn.instDecidableEqDynState.decEq Crn.DynState.pos1 Crn.DynState.pos1 = isTrue ⋯
- Crn.instDecidableEqDynState.decEq Crn.DynState.pos1 Crn.DynState.pos2 = isFalse Crn.instDecidableEqDynState.decEq._proof_19
- Crn.instDecidableEqDynState.decEq Crn.DynState.pos1 (Crn.DynState.weak x_2) = isFalse ⋯
- Crn.instDecidableEqDynState.decEq Crn.DynState.pos2 Crn.DynState.neg2 = isFalse Crn.instDecidableEqDynState.decEq._proof_21
- Crn.instDecidableEqDynState.decEq Crn.DynState.pos2 Crn.DynState.neg1 = isFalse Crn.instDecidableEqDynState.decEq._proof_22
- Crn.instDecidableEqDynState.decEq Crn.DynState.pos2 Crn.DynState.zero = isFalse Crn.instDecidableEqDynState.decEq._proof_23
- Crn.instDecidableEqDynState.decEq Crn.DynState.pos2 Crn.DynState.pos1 = isFalse Crn.instDecidableEqDynState.decEq._proof_24
- Crn.instDecidableEqDynState.decEq Crn.DynState.pos2 Crn.DynState.pos2 = isTrue ⋯
- Crn.instDecidableEqDynState.decEq Crn.DynState.pos2 (Crn.DynState.weak x_2) = isFalse ⋯
- Crn.instDecidableEqDynState.decEq (Crn.DynState.weak x_2) Crn.DynState.neg2 = isFalse ⋯
- Crn.instDecidableEqDynState.decEq (Crn.DynState.weak x_2) Crn.DynState.neg1 = isFalse ⋯
- Crn.instDecidableEqDynState.decEq (Crn.DynState.weak x_2) Crn.DynState.zero = isFalse ⋯
- Crn.instDecidableEqDynState.decEq (Crn.DynState.weak x_2) Crn.DynState.pos1 = isFalse ⋯
- Crn.instDecidableEqDynState.decEq (Crn.DynState.weak x_2) Crn.DynState.pos2 = isFalse ⋯
- Crn.instDecidableEqDynState.decEq (Crn.DynState.weak a) (Crn.DynState.weak b) = if h : a = b then h ▸ isTrue ⋯ else isFalse ⋯
Instances For
Equations
The weight [GHMSS16, Fig. 3]: w([z]) = z, w(⟨x⟩) = 0.
Equations
Instances For
The output (the reported sign of the colour sum) [GHMSS16, Section 3]: the sign of z in
[z], and x in ⟨x⟩.
Equations
Instances For
The strong state of weight z, for -2 ≤ z ≤ 2 (clamped outside this range).
Equations
- One or more equations did not get rendered due to their size.
Instances For
The new state of an agent in state a meeting an agent in state b, outside annihilations
[GHMSS16, Section 3]: a weak state, or [0] meeting a strong state of nonzero weight, becomes
the weak state of the sign of the strong state b (its output); otherwise nothing changes.
Equations
Instances For
The transition function of [GHMSS16, Section 3] (the text; Fig. 4 with its entry for [1]
meeting [0] corrected): opposite strong states annihilate ([1], [-1] and [2], [-2] into
[0], [0], [2], [-1] into [1], [0], [-2], [1] into [-1], [0]), all other encounters
recruit (recruit).
Equations
- Crn.DynState.δ (Crn.DynState.pos1, Crn.DynState.neg1) = (Crn.DynState.zero, Crn.DynState.zero)
- Crn.DynState.δ (Crn.DynState.neg1, Crn.DynState.pos1) = (Crn.DynState.zero, Crn.DynState.zero)
- Crn.DynState.δ (Crn.DynState.pos2, Crn.DynState.neg2) = (Crn.DynState.zero, Crn.DynState.zero)
- Crn.DynState.δ (Crn.DynState.neg2, Crn.DynState.pos2) = (Crn.DynState.zero, Crn.DynState.zero)
- Crn.DynState.δ (Crn.DynState.pos2, Crn.DynState.neg1) = (Crn.DynState.pos1, Crn.DynState.zero)
- Crn.DynState.δ (Crn.DynState.neg1, Crn.DynState.pos2) = (Crn.DynState.zero, Crn.DynState.pos1)
- Crn.DynState.δ (Crn.DynState.neg2, Crn.DynState.pos1) = (Crn.DynState.neg1, Crn.DynState.zero)
- Crn.DynState.δ (Crn.DynState.pos1, Crn.DynState.neg2) = (Crn.DynState.zero, Crn.DynState.neg1)
- Crn.DynState.δ (a, b) = (a.recruit b, b.recruit a)
Instances For
The state change forced by a colour change c → c' [GHMSS16, Fig. 3]: s ↦ [w(s) + c' - c]
if c ≠ c', nothing otherwise.
Equations
- Crn.DynState.recolour c c' s = if c = c' then s else Crn.DynState.ofWeight (s.weight + ↑c' - ↑c)
Instances For
The dynamic majority protocol P₂ [GHMSS16, Section 3] without the external force: input
colour x ↦ [x]. Its Bool output (more 1s than -1s) is not used; the outputs are
DynState.out.
Equations
- Crn.dynamicMajority = { input := fun (x : SignType) => Crn.DynState.ofWeight ↑x, output := fun (s : Crn.DynState) => decide (s.out = 1), δ := Crn.DynState.δ }
Instances For
The invariants of [GHMSS16, Section 3] for the colours col and the states c, group by
group: (1) in every group the colour sum equals the weight sum; (2) |w(s_a) - c_a| ≤ 1 for every
agent; and (3) every group contains a strong state. (3) is not stated in the paper but used in the
tie case of its final argument (an agent in state [0] must remain); it holds initially and is
preserved.
- sum_eq (v : Fin n) : ∑ u : Fin n with grp u = grp v, ↑(col u) = ∑ u : Fin n with grp u = grp v, (c u).weight
Invariant 1, in every group.
Invariant 2.
Every group contains a strong state.
Instances For
The initial configuration [c_a] satisfies the invariants.
A strong state a of weight sign s recruits every state of weight 0 or of sign s that
does not report s into ⟨s⟩, and keeps its state.
A strong state reports the sign of its weight.
Sums over a group across an encounter inside a group: if the encounter preserves
F a + F b, the sum of F over every group is preserved.
[GHMSS16, Lemma 4], interactions. Steps inside groups preserve the invariants (the colours do not change).
[GHMSS16, Lemma 4], the external force. Changing the colour of agent v to x and its
state by DynState.recolour preserves the invariants.
[GHMSS16, Lemma 5], second part. Interactions inside groups reach a configuration in which no two agents of the same group have weights of opposite signs.
The invariants hold along every execution inside groups.
[GHMSS16, Section 3, after Lemma 5] Stabilization of the dynamic majority protocol. From a
configuration satisfying the invariants, interactions inside groups reach a configuration from
which, along every further execution inside groups, every agent outputs the sign of the colour sum
of its group (1: more 1s, -1: more -1s, 0: a tie).
An interaction of P₂ (the colours are unchanged) or a colour change of one agent by the
external force (with the state change of Fig. 3), on pairs (colours, states).
Equations
- One or more equations did not get rendered due to their size.
Instances For
[GHMSS16, Section 3] The dynamic majority protocol with the external force. Start from the
colours ι in the states [ι a], and let interactions and colour changes alternate arbitrarily,
reaching the colours col and the states c. If the force stops there, the protocol reaches a
configuration that is output-stable with the sign of the final colour sum at every agent.
Without the external force, the dynamic majority protocol stably computes the sign of
#1 - #(-1), like the static one.