- Boxes
- definitions
- Ellipses
- theorems and lemmas
- Blue border
- the statement of this result is ready to be formalized; all prerequisites are done
- Orange border
- the statement of this result is not ready to be formalized; the blueprint needs more work
- Blue background
- the proof of this result is ready to be formalized; all prerequisites are done
- Green border
- the statement of this result is formalized
- Green background
- the proof of this result is formalized
- Dark green background
- the proof of this result and all its ancestors are formalized
- Dark green border
- this is in Mathlib
Species \(X\), \(Y\) (the two opinions) and \(B\) (blank), and the reactions \(X + Y \to X + B\), \(X + Y \to Y + B\), \(B + X \to X + X\), \(B + Y \to Y + Y\) (Angluin, Aspnes and Eisenstat).
The one-way rule: the initiator never changes; an initiator \(X\) or \(Y\) turns an opposite responder blank and recruits a blank responder. Its effective transitions are exactly the reactions of the approximate-majority network. Each step activates a uniformly random oriented edge of \(G\).
A state is a color and a bit saying whether the vertex holds an ambassador; every agent starts with an ambassador of its input color, and the output is the color. Two ambassadors of different colors annihilate; an ambassador meeting a vertex without ambassador moves there and paints it; nothing else changes. This is the table of Figure 1, with \(4\) states, and the protocol is symmetric.
A reaction \(A + B \to C + D\) consumes the unordered pair \(\{ A, B\} \) of species and produces the unordered pair \(\{ C, D\} \); a network is a nonempty finite set of reactions whose products differ from their reactants. A count vector of \(n\) molecules gives the number \(x_a\) of molecules of each species \(a\), with \(\sum _a x_a = n\); firing an applicable reaction \(r\) replaces \(x_a\) by \(x_a - \nu _a + \nu '_a\), with \(\nu \), \(\nu '\) the reactant and product multiplicities.
A network with an injective input map \(I : X \to S\) and an output map \(O : S \to \{ 0, 1\} \) stably decides \(\varphi \) if, from the initial count vector with \(x_i\) molecules of \(I(i)\) and nothing else, every reachable count vector can reach one in which, now and in every count vector reachable from it, every present species votes \(\varphi (x)\).
Every agent keeps its label \(l\) and runs \(k\) copies of the static protocol on the bits \(l[i]\), read as \(\pm 1\). They drive a copy of the dynamic protocol, with colour \(1\) if every copy currently reports the agent’s own bit and \(-1\) otherwise. An agent outputs the reported majority bits if its dynamic protocol outputs \(1\), and none otherwise. The specification is the colour held by more than half of the agents, if any.
Given a protocol \(D\), a colour map from its states to \(\{ -1, 0, 1\} \) and a group map that \(D\) never changes, the driven protocol runs \(D\) and a copy of the dynamic protocol: in an encounter \(D\) makes its transition, the dynamic protocol makes its transition if the two agents are in the same group, and each agent whose colour changed applies the state change of the force.
The eight states are the strong states \([-2], \dots , [2]\) and the weak states \(\langle -1 \rangle , \langle 0 \rangle , \langle 1 \rangle \). Opposite strong states cancel as far as possible, and strong states recruit weak ones and \([0]\) as in the static protocol; the transitions do not read the colours. When an external force changes a colour \(c\) to \(c'\), the state becomes \([w + c' - c]\), \(w\) its weight. For Section 5 the protocol runs separately in groups of agents, with encounters inside a group.
In every group the colour sum equals the weight sum, every agent’s weight is within \(1\) of its colour, and every group contains a strong state. The initial configuration \([c_a]\) satisfies them.
For an output map \(O : Q \to Y\) into any type and a target \(g(x, i) \in Y\) depending on the input counts \(x\) and on an agent’s input \(i\), a protocol stably marks the agents with \(g\) if, for every nonempty population, every configuration reachable from the initial one can reach a configuration from which every agent \(v\) forever outputs \(g(x, \iota (v))\). Stable computation of \(f\) is the case \(g(x, i) = f(x)\); with the protocol’s Boolean output it is Definition 14.
Stages \(i = k - 1, \dots , 0\): the agents whose labels share the prefix \(l[0..i-1]\) form a group, and a copy of the dynamic protocol runs in each group, with colour \(l[i]\) (as \(\pm 1\)) for the agents that won all the stages above \(i\) and \(0\) for the others. An agent wins stage \(i\) if its colour is \(-1\) and the stage outputs \(-1\), or its colour is \(1\) and the stage outputs \(0\) or \(1\). The protocol is the \(k\)-fold iteration of the driven protocol, the colours being derived from the states. The plurality colour is the most frequent one, ties broken in favour of the lexicographically largest label.
Colours are in \(\{ -1, 0, 1\} \). The six states are the strong states \([x]\) and the weak states \(\langle x \rangle \), \(x \in \{ -1, 0, 1\} \), of weight \(x\) and \(0\). The states \([1]\) and \([-1]\) annihilate into \([0], [0]\); a strong \([x]\) turns a weak state into \(\langle x \rangle \), and, for \(x \ne 0\), turns \([0]\) into \(\langle x \rangle \). The output of \([x]\) and \(\langle x \rangle \) is \(x\).
On a graph \(G\) on the agents, an encounter is an oriented edge \((u, v)\) of \(G\) (initiator \(u\), responder \(v\)). Reachability and output stability on \(G\) are defined as before with encounters along edges of \(G\). A protocol stably computes \(\varphi \) on \(G\) for inputs in a domain \(D\) if, for every input whose count vector lies in \(D\), every configuration reachable on \(G\) can reach an output-stable configuration with output \(\varphi \); it stably computes \(\varphi \) on graphs if it does so on every connected graph.
From \(x\) with \(a_0(x) {\gt} 0\) the jump chain fires \(r\) with probability \(a_r(x)/a_0(x)\); from a terminal state (\(a_0(x) = 0\)) it stays put.
With two input types, red and green, majority is true if red has more agents than green, and the domain excludes ties.
Each of \(n \ge 2\) agents holds a species. One interaction draws a uniformly random ordered pair \((u, v)\) of distinct agents and, independently, a uniformly random reaction \(r\) of the network; if the species of \(u\) and \(v\) are the reactants of \(r\) the pair reacts and \(r\) fires, otherwise nothing changes. The protocol is observed on count vectors; conditioning on the pair reacting gives a kernel on count vectors.
With rate constant \(k\), the propensity of \(r\) at \(x\) is \(a_r(x) = k \prod _a \binom {x_a}{\nu _a}\) (Gillespie’s combinatorial form), and \(a_0(x) = \sum _r a_r(x)\).
A population protocol has an input function \(I : X \to Q\), an output function \(O : Q \to \{ 0, 1\} \) and a transition function \(\delta : Q \times Q \to Q \times Q\). An encounter of an ordered pair \((u, v)\) of distinct agents replaces their states \(p, q\) by \(\delta (p, q)\); reachability is the reflexive-transitive closure of encounters. A configuration is output-stable with output \(b\) if in every configuration reachable from it every agent outputs \(b\).
A protocol stably computes a predicate \(\varphi \) on input count vectors if, for every nonempty population and every input assignment \(\iota \), every configuration reachable from \(I \circ \iota \) can reach an output-stable configuration with output \(\varphi \) of the input counts. A predicate is stably computable if a protocol with finitely many states stably computes it.
With \(m\) agents of type \(Y\) placed on a uniformly random \(m\)-set and \(X\) elsewhere, \(\mathrm{win}_t(s)\) is the probability that every agent is \(s\) at time \(t\). Unanimity is absorbing, so \(\mathrm{win}_t(s)\) is nondecreasing in \(t\), and its supremum, the convergence probability, is its limit.
For the order \(Y {\lt} B {\lt} X\) the rule is monotone in both states, so the probability that every agent is \(X\) at time \(t\) is monotone in the initial configuration. Exchanging \(X\) and \(Y\) commutes with the dynamics.
The number of ambassadors of each color starts at the input count and never increases, and the difference between red and green ambassadors never changes.
On a connected graph, while both colors have ambassadors, a configuration with one ambassador of each color fewer is reachable. If all ambassadors have color \(b\) and there is one, the all-\(b\) coloring is reachable, and it is output-stable.
Once the stages above \(i\) have stabilized, the duel of stage \(i\) between the winners of the two groups extending a prefix \(p\) selects the winner of the group of \(p\). The winner of the whole population is the plurality colour.
The invariants are preserved by encounters inside groups and by colour changes. The sum of the absolute weights does not increase, and a configuration without opposite weights in a group is reachable.
Along every execution the weight sum equals the colour sum \(S\), the sum \(R\) of the absolute weights does not increase, and a configuration with \(R = |S|\) is reachable.
A family of \(r\)-element subsets of a finite universe, with at most as many sets as elements, in which every element lies in the same number \(d \ge 1\) of sets, has a system of distinct representatives. In particular, if \(n \le 2m\), every \(m\)-set \(S\) of agents contains an \((n - m)\)-subset \(A_S\), with \(S \mapsto A_S\) injective on the \(m\)-sets.
The drawn pair has species \(\{ A, B\} \) with probability \(x_A x_B / \binom {n}{2}\) if \(A \ne B\), and \(\binom {x_A}{2} / \binom {n}{2}\) if \(A = B\). Equivalently, it has the reactants of \(r\) with probability \(a_r(x) / (k \binom {n}{2})\).
For \(A + B \to \cdots \) with \(A \ne B\) the propensity is \(k\, x_A x_B\); for \(A + A \to \cdots \) it is \(k \binom {x_A}{2}\).
With \(D = 2 x_X x_Y + x_B (x_X + x_Y) {\gt} 0\), the jump chain fires each \(X + Y\) reaction with probability \(x_X x_Y / D\), \(B + X \to X + X\) with probability \(x_B x_X / D\) and \(B + Y \to Y + Y\) with probability \(x_B x_Y / D\); a drawn pair reacts with probability \(D / (4 \binom {n}{2})\); and the jump chain is the population protocol conditioned on reacting.
On every graph with an edge, if \(n \le 2m\), at every time \(t\) the probability that the minority \(X\) has won is at most the probability that the majority \(Y\) has won; hence the same holds for the convergence probabilities.
On a connected graph, from every configuration with a non-blank agent, the protocol is absorbed in all-\(X\) or all-\(Y\) with probability tending to \(1\). Hence, if \(n \le 2m\) and \(m \le n\), it converges to the majority with probability at least \(1/2\).
The ambassador protocol stably computes majority on every connected graph, for every input with a majority. With one red and one green agent, a configuration is reachable from which no output-stable configuration is reachable, so ties must be excluded.
For every Boolean function \(\xi \) of two arguments, if \(\varphi \) and \(\psi \) are stably computable then so is \(\xi (\varphi , \psi )\); in particular the class is closed under negation, conjunction and disjunction.
For every rate constant \(k {\gt} 0\) and \(n \ge 2\), the population protocol conditioned on the drawn pair reacting is the jump chain of mass-action kinetics, from every configuration and hence as kernels on count vectors.
One interaction of the population protocol is a kernel on count vectors. Its jump chain (the step conditioned on changing the counts, Dynamics.Kernel.jump) is the jump chain of mass-action kinetics, which is its own jump chain; so the protocol and the network have the same jump chain, and the protocol conditioned on reacting is the jump chain of the protocol. This holds in particular for the approximate-majority network.
Absolute-Majority stably computes the absolute majority colour, or reports that there is none, with \(2^k \cdot 6^k \cdot 8 \le 2^{4k+3}\) states.
Along every execution of the driven protocol the invariants of Section 3 hold for the derived colours. If \(D\) stably marks the agents with their eventual colours, the driven protocol stably marks every agent with the sign of the eventual colour sum of its group.
From every configuration satisfying the invariants, a configuration is reachable from which every agent forever outputs the sign of the colour sum of its group. Hence after any finite interleaving of encounters and colour changes the dynamic protocol stabilizes on the sign of the final colour sum, and without the force it stably computes \(\operatorname {sign}(\# 1 - \# (-1))\).
Relative-Majority stably marks the agents of the plurality colour: eventually and forever, every agent outputs whether its own colour is the plurality colour. It has \(2^k \cdot 8^k = 2^{4k}\) states.
For integers \(a_i\), \(c\) and \(m {\gt} 0\), the predicate \(\sum _i a_i x_i \equiv c \pmod m\) is stably computable.
The truth set of every such predicate is a semilinear set of count vectors, and every such predicate is stably computable.
The drawn pair reacts with probability \(p = a_0(x) / (k\, |N| \binom {n}{2})\), and one interaction is a jump of the mass-action chain with probability \(p\) and a no-op otherwise.
For integers \(a_i\) and \(c\), the predicates \(\sum _i a_i x_i {\lt} c\) and \(\sum _i a_i x_i \ge c\) are stably computable.
The transitions \(p + q \to \delta _1(p, q) + \delta _2(p, q)\) that change \(\{ p, q\} \) form a count-conserving bimolecular network whose reachable count vectors are the counts of the configurations reachable in the protocol. Hence every stably computable predicate, and in particular every Boolean combination of threshold and remainder predicates, is stably decided by such a network.