Relative majority (plurality) with O(k)-bit states (CRN-5, [GHMSS16, Section 5]) #
Algorithm Relative-Majority [GHMSS16, Section 5.1]. Colours are k-bit labels; the winner is the
most frequent label, ties broken in favour of the lexicographically largest label (bit 0 first,
-1 < 1, i.e. false < true: IsPlurality). Stages i = k-1, …, 0: in stage i, the agents
whose labels share the prefix l[0..i-1] form a group, and a copy P₂(i) of the dynamic
majority protocol runs inside each group, with colour c[i] = l[i] (as ±1) for the agents whose
label won all stages > i (the winner of the group of prefix l[0..i]) and c[i] = 0 for the
others. An agent wins stage i if c[i] = -1 and P₂(i) outputs -1, or c[i] = 1 and P₂(i)
outputs 0 or 1 (a tie goes to the larger label, wins).
Formalization: the protocol is the k-fold iteration of Protocol.drive
(ExactMajorityCompose.lean). Level 0 keeps the label; level m + 1 drives P₂(k-1-m) by level
m through the colour stageColour (computed from the label and from whether the agent won the
stages k-1, …, k-m), in the groups of the prefixes of length k-1-m. The colours c[i] are
derived from the states rather than stored, so a change propagates through all lower stages within
the same encounter, as described in [GHMSS16, Section 5.1, Stabilisation Stage 2]. At the end
(level k), every agent knows whether its own colour is the winner (RelState.won): the protocol
marks the agents of the winning colour [GHMSS16, Section 5].
Main statements:
duel_wins_iff(one stage of the proof of Theorem 7): the duel of stageibetween the group winners of the prefixesp·(-1)andp·1selects the winner of the group of prefixp.relativeMajority_level_stablyMarks(the induction of the proof of Theorem 7).relativeMajority_stablyMarks(Theorem 7).card_relState(Theorem 7, space):2^k · 8^k = 2^(4k)states, i.e.4kbits.
The states of level m of Relative-Majority: the label and the states of P₂ at the stages
k-1, …, k-m (the last one outermost).
Equations
- Crn.RelState k 0 = Crn.Label k
- Crn.RelState k m.succ = (Crn.RelState k m × Crn.DynState)
Instances For
Finitely many states.
Equations
- Crn.RelState.instFintype k 0 = { elems := Crn.RelState.instFintype._aux_1 k, complete := ⋯ }
- Crn.RelState.instFintype k m.succ = instFintypeProd (Crn.RelState k m) Crn.DynState
The prefix L[0..j-1] of a label, padded with false: two labels have the same prefix of
length j iff their prefixMasks agree.
Instances For
Whether an agent with colour c for a stage, whose P₂ reports o, wins the stage
[GHMSS16, Section 5.1, Stabilisation Stage 2]: c = -1 and o = -1, or c = 1 and
o ∈ {0, 1} (a tie goes to the lexicographically larger label).
Instances For
Whether the agent's label won all stages so far (true at level 0; at level m + 1, it won
the stages before and wins stage k-1-m against the report of its P₂(k-1-m)).
Equations
Instances For
The colour c[k-1-m] of an agent at level m [GHMSS16, Section 5, memory organisation (2)]:
its bit l[k-1-m] as ±1 if it won all stages so far, 0 otherwise.
Equations
Instances For
Level m of Relative-Majority: the label alone at level 0; at level m + 1, the dynamic
majority protocol P₂(k-1-m) driven by level m through stageColour, inside the groups of the
prefixes of length k-1-m [GHMSS16, Section 5.1].
Equations
- Crn.relativeMajorityLevel k 0 = { input := id, output := fun (x : Crn.RelState k 0) => true, δ := id }
- Crn.relativeMajorityLevel k m.succ = (Crn.relativeMajorityLevel k m).drive Crn.stageColour fun (q : Crn.RelState k m) => Crn.prefixMask q.label (k - 1 - m)
Instances For
Algorithm Relative-Majority [GHMSS16, Section 5.1]: all k stages.
Equations
Instances For
L wins its group of prefix length j: among the labels with the same prefix L[0..j-1], L
is the most frequent, ties broken by the lexicographic order.
Equations
- Crn.IsGroupWinner x j L = ∀ (L' : Crn.Label k), Crn.prefixMask L' j = Crn.prefixMask L j → x L' < x L ∨ x L' = x L ∧ toLex L' ≤ toLex L
Instances For
L is the relative majority (plurality) colour [GHMSS16, Section 5]: the most frequent
colour, the lexicographically largest one among several most frequent colours.
Instances For
Equations
Equations
The colour at stage i of an agent with label L once the stages > i are stable: L[i] as
±1 if L won its group of prefix length i + 1, 0 otherwise.
Equations
- Crn.duelColour x i L = if Crn.IsGroupWinner x (i + 1) L then Crn.bitSign (Crn.bitAt L i) else 0
Instances For
[GHMSS16, proof of Theorem 7], one stage. In the group of the prefix L[0..i-1], the
sum of the stage-i colours is #W₁ - #W₋₁, W_{±1} the winners of the subgroups of prefixes
L[0..i-1]·(±1); the agent with label L wins the duel iff L wins its group of prefix length
i.
The winner of the group of prefix length 0 is the plurality colour.
The initial state of every level carries the input label.
Level 0 never changes a configuration.
The prefix of length k is the whole label.
Every label wins its group of prefix length k (the group of the label alone).
[GHMSS16, proof of Theorem 7], the induction on stages. For m ≤ k, level m stably
marks every agent with its label and with whether its label wins its group of prefix length
k - m (i.e. the stages k-1, …, k-m have stabilized).
[GHMSS16, Theorem 7] Algorithm Relative-Majority stably marks the agents of the
relative majority colour: eventually and forever, an agent outputs true iff its colour is the
most frequent one (the lexicographically largest among several most frequent ones).
Level m has 2^k · 8^m states.