Documentation

Crn.GraphMajorityLowerBound

At least 4 states are needed for majority (CRN-4) #

[MNRS14, Theorem 1]: no population protocol with at most 3 states stably computes the majority of a 2-type population on every interaction graph, so the 4-state ambassador protocol (ambassador_graphStablyComputes) has the minimal number of states.

The paper's proof only uses complete interaction graphs (a population V and the population V ∪ {u, v} with two extra agents, interacting in a supergraph), so we pin the stronger form not_stablyComputesOnGraph_top_majority: no protocol with at most 3 states stably computes majority on the complete graphs of all nonempty populations (the standard populations of Protocol.StablyComputes), even with ties excluded from the domain. The statement on all connected graphs follows (not_graphStablyComputes_majority).

Proof route [MNRS14, Theorem 1]: both outputs occur, so with at most 3 states one output value b has a single state q₁. Say b is the output of a red majority (otherwise exchange the colors). On V = Fin 3, the inputs C₁ = (r, r, g) and C₂ = (r, r, r) both reach the configuration "all q₁". Adding two green agents gives C₁' = (r, r, g, g, g) (green majority) and C₂' = (r, r, r, g, g) (red majority); running the same encounters inside V (Protocol.GraphReaches.extend) both reach the configuration "q₁ on V, green input state on the two extra agents", from which output-stable configurations with both outputs would be reachable: a contradiction. The paper takes |V| = 2k + 1 with k ≥ 2; k = 1 already works.

References #

theorem Crn.Protocol.GraphReaches.eq_of_fin_one {Q : Type u_1} {P : Protocol Bool Q} {c d : Fin 1 → Q} (h : P.GraphReaches ⊤ c d) :
d = c

A single agent has no partner on the complete graph: from c, only c is reachable.

Both outputs occur [MNRS14, proof of Theorem 1]: a protocol computing majority on the complete graph of a single agent outputs b on the input state of b.

theorem Crn.not_stablyComputesOnGraph_top_majority_of_unique {Q : Type u_1} (P : Protocol Bool Q) (b : Bool) (q₁ : Q) (hq : ∀ (q : Q), P.output q = b → q = q₁) :

The core of [MNRS14, Theorem 1]. If a single state q₁ has output b, then the protocol does not compute majority on all complete graphs: on Fin 3, the inputs (b, b, !b) and (b, b, b) both reach "all q₁"; adding two agents of input !b (inputs (b, b, !b, !b, !b) and (b, b, b, !b, !b), with majorities !b and b) gives a common reachable configuration from which output-stable configurations with both outputs are reachable.

[MNRS14, Theorem 1], strong form. No population protocol with at most 3 states stably computes the majority of two input types on the complete graphs of all nonempty populations, with the tie inputs excluded from the domain.

[MNRS14, Theorem 1]. No population protocol with at most 3 states stably computes the majority of two input types on every connected interaction graph: R(𝒫_majority) > 3.

The rank of majority is 4 [MNRS14, Theorems 1 and 2]: the 4-state ambassador protocol stably computes majority on every connected graph, and no protocol with fewer states does.