The 4-state ambassador protocol computes majority on every connected graph (CRN-4) #
The ambassador protocol of [MNRS14, §4] has the states (color, ambassador) : Bool × Bool
(true is red r, false is green g; the second component says whether the vertex holds an
ambassador). An input x starts in (x, true) and the output is the color. On an encounter:
- two ambassadors of different colors annihilate (both vertices keep their colors);
- an ambassador meeting a vertex without ambassador moves there and paints it with its color;
- nothing else changes.
The protocol is symmetric (ambassador_symm): it does not distinguish initiator and responder.
Its transition table is Figure 1 of [MNRS14] (ambassador_table).
Theorem 2 of [MNRS14] (ambassador_graphStablyComputes): on every connected graph, if
there is initially a majority, the ambassador protocol stably computes it. The proof pins:
- the invariants: the number of ambassadors of each color never increases
(
ambCount_interact_le) and their difference never changes (ambCount_sub_interact); it starts at the input counts (ambCount_input); - annihilation is always reachable while both colors have ambassadors
(
exists_reaches_annihilate, the step𝒞_{k,ℓ} → 𝒞_{k−1,ℓ−1}of the proof); - once all ambassadors have color
band there is one, the all-bcoloring is reachable (exists_reaches_allColor); - a configuration in which every vertex has color
bis output-stable with outputb(graphOutputStable_of_allColor).
The tie case is excluded exactly as in the paper (domain HasMajority); without it the
protocol can get stuck in a configuration with both colors and no ambassadors
(ambassador_tie_stuck).
References #
- [MNRS14] G. B. Mertzios, S. E. Nikoletseas, C. L. Raptopoulos, P. G. Spirakis, Determining majority in networks with local interactions and very small local memory, ICALP 2014; arXiv:1404.7671.
The states of the ambassador protocol [MNRS14, §4]: a color (true red, false green) and
whether the vertex holds an ambassador.
Equations
- Crn.AmbState = (Bool × Bool)
Instances For
The transition function of the ambassador protocol [MNRS14, §4, Figure 1], on the states of (initiator, responder).
Equations
- Crn.ambassadorδ ((c₁, true), c₂, true) = if c₁ = c₂ then ((c₁, true), c₂, true) else ((c₁, false), c₂, false)
- Crn.ambassadorδ ((c₁, true), fst, false) = ((c₁, false), c₁, true)
- Crn.ambassadorδ ((fst, false), c₂, true) = ((c₂, true), c₂, false)
- Crn.ambassadorδ ((c₁, false), c₂, false) = ((c₁, false), c₂, false)
Instances For
The 4-state ambassador protocol [MNRS14, §4]: input x ↦ (x, true) (every vertex starts
with an ambassador of its own color), output the color.
Equations
- Crn.ambassador = { input := fun (x : Bool) => (x, true), output := fun (s : Crn.AmbState) => s.1, δ := Crn.ambassadorδ }
Instances For
The ten nontrivial entries of the transition table [MNRS14, Figure 1], with r = true,
g = false; all other entries leave both states unchanged (ambassador_table_rest).
The ambassador protocol is symmetric [MNRS14, §2 and §4].
Every transition removes as many red as green ambassadors.
Invariant [MNRS14, proof of Theorem 2: "whenever ambassadors disappear, they disappear in pairs, i.e. one from each color"]: the difference between the numbers of red and green ambassadors never changes.
Annihilation is reachable, by induction on the distance k from a red ambassador at u to a
green ambassador at w: the red ambassador walks towards w along a shortest path (moving to
free vertices, or handing over to a red ambassador it meets) until it meets a green one.
Spreading the color b by one vertex, by induction on the distance k from an ambassador
of color b at u to a vertex w of color !b, in the absence of ambassadors of color !b:
the ambassador walks towards w along a shortest path (handing over to the ambassadors of color
b it meets) until it paints a vertex of color !b.
Annihilation is reachable [MNRS14, proof of Theorem 2: every configuration of 𝒞_{k,ℓ}
with k, ℓ ≥ 1 can lead to 𝒞_{k−1,ℓ−1}]: on a connected graph, while both colors have an
ambassador, a configuration with one ambassador fewer of each color is reachable.
Spreading is reachable [MNRS14, proof of Theorem 2: from 𝒞_{k−ℓ,0} "there exists a
chain of transitions that lead to a configuration where all vertices are colored with the color
of the initial majority"]: on a connected graph, if there is an ambassador of color b and none
of the other color, the configuration in which every vertex has color b is reachable.
A configuration in which every vertex has color b is output-stable with output b, on
every interaction graph: encounters of two vertices of color b keep color b.
The difference between the numbers of red and green ambassadors is invariant along
reachability on any interaction graph (ambCount_sub_interact).
Iterated annihilation [MNRS14, proof of Theorem 2: 𝒞_{k,ℓ} → ⋯ → 𝒞_{k−ℓ,0}]: on a
connected graph, a configuration in which some color has no ambassador is reachable.
[MNRS14, Theorem 2]. Given any connected graph, if there exists initially a majority, the 4-state ambassador protocol stably computes the initial majority value.
[MNRS14, Theorem 2] on the complete graph of every nonempty population (the standard
population of Protocol.StablyComputes).
A configuration without ambassadors is a fixed point on every interaction graph: every
encounter of two vertices without ambassador leaves both unchanged (ambassador_table_rest).
The tie case is excluded (as in [MNRS14, Theorem 2]): on the complete graph of two agents with one red and one green input, the protocol reaches a configuration (both ambassadors annihilated, both colors present) from which no output-stable configuration is reachable.