Absolute majority with O(k)-bit states (CRN-5, [GHMSS16, Section 4]) #
Colours are k-bit labels L : Fin k → Bool (Label k; [GHMSS16] reads the bits as ±1,
bitSign); a population with C ≤ 2^k colours uses C of the labels. Algorithm
Absolute-Majority [GHMSS16, Section 4.1]: every agent keeps its label l, runs k independent
copies P₁(i) of the static majority protocol on the bits l[i] (bitsProtocol), and a copy of
the dynamic majority protocol P₂ whose colour is 1 if the agent's label agrees with all the
majority bits currently reported by its P₁(i), and -1 otherwise (absColour); P₂ decides
whether the label of the reported majority bits is held by more than half of the agents. An agent
outputs some L*, L* the reported majority bits, if its P₂ outputs 1, and none otherwise
(absOutput).
Main statements:
bitsProtocol_stablyMarks([GHMSS16, Section 4]): thekcopies ofP₁stably compute thekmajority bits (majBit).absTarget_sum_sign_eq_one_iff,majBit_eq_of_isAbsMajority(the combinatorial part of the proof of Theorem 6).absoluteMajority_stablyComputes(Theorem 6): the protocol stably computes the absolute majority colour, or reports that there is none (absMajority).card_absState(Theorem 6, space):2^k · 6^k · 8 ≤ 2^(4k+3)states, i.e.4k + 3bits.
The k independent copies P₁(0), …, P₁(k-1) of the static majority protocol on the bits of
the labels, the label being kept [GHMSS16, Section 4, memory organisation (1)–(2)]. The Bool
output is not used.
Equations
- One or more equations did not get rendered due to their size.
Instances For
The majority bit i of the input counts x: the sign of #(bit i = 1) - #(bit i = 0), the
output of P₁(i).
Equations
- Crn.majBit x i = SignType.sign (∑ L : Crn.Label k, ↑(x L) * ↑(Crn.bitSign (L i)))
Instances For
Component i of an encounter of bitsProtocol is an encounter of P₁.
Encounters of bitsProtocol keep the labels.
Paths of bitsProtocol project to paths of P₁ in every component.
Paths of bitsProtocol keep the labels.
A path of P₁ in component i lifts to bitsProtocol (same encounters).
[GHMSS16, Section 4] The k copies of P₁ stably compute the k majority bits, and
every agent keeps its label.
The colour of an agent for P₂ [GHMSS16, Section 4.1, Initialisation Stage 2]: 1 if every
P₁(i) currently reports the agent's own bit l[i] as the majority bit, -1 otherwise.
Equations
- Crn.absColour q = if ∀ (i : Fin k), (q.2 i).out = Crn.bitSign (q.1 i) then 1 else -1
Instances For
Algorithm Absolute-Majority [GHMSS16, Section 4.1]: P₂ driven by the k copies of P₁
through absColour, in a single group.
Equations
- Crn.absoluteMajority k = (Crn.bitsProtocol k).drive Crn.absColour fun (x : Crn.Label k × (Fin k → Crn.StaticState)) => ()
Instances For
The output of Absolute-Majority: some L*, L* the majority bits reported by the copies of
P₁, if P₂ reports colour 1 in the majority; none (no absolute majority) otherwise.
Equations
Instances For
The absolute majority colour of the counts x, or none if there is none.
Equations
- Crn.absMajority x = if h : ∃ (L : Crn.Label k), Crn.IsAbsMajority x L then some h.choose else none
Instances For
There is at most one absolute majority colour, and absMajority returns it.
The eventual colour for P₂ of an agent with label L: 1 if L agrees with all majority
bits, -1 otherwise.
Equations
- Crn.absTarget x L = if ∀ (i : Fin k), Crn.majBit x i = Crn.bitSign (L i) then 1 else -1
Instances For
The majority bits of an absolute majority colour are its bits (the proof of
majBit_eq_of_isAbsMajority).
[GHMSS16, proof of Theorem 6] The final test of P₂: the eventual colour sum
#(L = L*) - #(L ≠ L*) is positive iff some colour is an absolute majority (it is then L*).
[GHMSS16, Theorem 6] Algorithm Absolute-Majority stably computes the absolute majority:
all agents eventually and forever output some L if more than half of the agents have colour L,
and none if there is no such colour.