3-input rules that solve plurality consensus (Section 4.2) #
A 3-input rule f : Fin k → Fin k → Fin k → Fin k is applied by every node
to the colors of its three samples (stepWith f). The paper characterizes the
rules that solve plurality consensus by two properties:
- clear majority: whenever two of the three colors agree,
freturns that color; - uniform: for three distinct colors
r, g, b, each of them is returned on exactly two of the six orderings of(r, g, b).
This file contains the definitions and the tools shared by the two parts of
Theorem 4.8: the counts Δ and δ, the solver predicate, and the fact that
consensus on a color is impossible once that color has disappeared
(mono_le_alive).
A 3-input rule.
Instances For
Δ_r for the pair (r, b): on how many of the three orderings of
(r, r, b) the rule returns r.
Equations
Instances For
Uniform property (Definition 4.5).
Equations
- Plurality.UniformRule f = ∀ (r g b : Fin k), r ≠ g → g ≠ b → r ≠ b → Plurality.deltaCount f r g b r = 2
Instances For
(s, ε)-solver (Definition 4.7): from every coloring in which m is
the unique plurality color with bias at least s, the probability that all
nodes eventually support m is at least 1 - ε. Consensus is absorbing, so
"eventually" is the supremum over the horizon T.
Equations
- One or more equations did not get rendered due to their size.
Instances For
The counts of the three distinct colors sum to 6.
δ does not depend on the order in which the triple is listed.
Absorption for conservative rules #
Consensus needs survival. For every horizon T, the probability of
consensus on m at time T is at most the probability that m still has a
node at any fixed time T₀.