3-Majority and Voter with any number of colours (roadmap MAJ-6, part (b)) #
Model of Berenbrink, Clementi, Elsässer, Kling, Mallmann-Trenn, Natale, Ignore or Comply? On
breaking symmetry in consensus, PODC 2017, arXiv:1702.04921 (v1), Section 2.1. Each of n
agents holds a colour of an arbitrary type σ; the paper's colours [k] ⊆ [n] are σ = Fin n.
majColour c s: the 3-Majority rule of Section 2.2 on a sample triples. The paper adopts a colour supported by at least two samples, and otherwise a uniformly random one of the three samples. Here a three-way tie adopts the first sample: since the three samples are i.i.d., this has the same law (the process function of Equation (2),alpha3M_weight), and it keeps the round randomnessTgt3 nof the two-opinion model.stepCol,runCol: one round and a whole trajectory of 3-Majority, on the round typeTgt3 nofThreeMajority.Model. With two colours this is the two-opinionstep(stepCol_bool), so the model is the two-opinion one, extended to any number of colours. This is the one definition of the 3-Majority round with colours: the roundPlurality.stepof the libraryPluralityisstepColat coloursFin k(Plurality.step_eq_stepCol, byrfl), and its bridge to the two-opinion model is derived fromstepCol_bool.voterStep,voterRun: the Voter process (Equation (1)); a round isFin n → Fin n, every agent pulling the colour of one uniformly random agent (itself included).colourCount c a,numColours c: the configuration vector of the paper and the number of remaining colours.
One round of the Voter process (BCEKMN17, Section 2.2, Equation (1)): agent v adopts the
colour of agent y v.
Equations
- ThreeMajority.voterStep c y v = c (y v)
Instances For
The configuration of the Voter process after consuming a list of rounds.
Equations
- ThreeMajority.voterRun c [] = c
- ThreeMajority.voterRun c (y :: l) = ThreeMajority.voterRun (ThreeMajority.voterStep c y) l
Instances For
The 3-Majority update rule on a sample triple s = (s₁, s₂, s₃) (BCEKMN17, Section 2.2):
if the second and third samples agree, adopt their colour (a majority); otherwise the first
sample's colour is a majority or all three colours differ, and the first sample's colour is
adopted.
Instances For
One round of 3-Majority with any number of colours (BCEKMN17, Section 2.2).
Equations
- ThreeMajority.stepCol c r v = ThreeMajority.majColour c (r v)
Instances For
The configuration of 3-Majority after consuming a list of rounds.
Equations
- ThreeMajority.runCol c [] = c
- ThreeMajority.runCol c (r :: l) = ThreeMajority.runCol (ThreeMajority.stepCol c r) l
Instances For
The number c_a of agents of colour a: the configuration vector of BCEKMN17,
Section 2.1.
Equations
- ThreeMajority.colourCount c a = {v : Fin n | c v = a}.card
Instances For
The number of remaining colours of a configuration. Consensus is numColours c ≤ 1.
Equations
Instances For
Renaming the colours by an injective map commutes with a round: the rule only compares colours.
3-Majority never creates a colour: the colours after a round are among the current ones.
The number of colours of 3-Majority never increases along a trajectory; hence the event
"at most κ colours at time T" is the event "at most κ colours by time T", and fixed-time
bounds are bounds on the hitting times T^κ of the paper.