Chemical Reaction Networks and Population Protocols
1 Chemical reaction networks
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.
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)\).
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}\).
Only the reactant species have nonzero multiplicity in the product.
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.
If \(a_0(x) \ne 0\), the jump chain from \(x\) gives weight \(0\) to \(x\).
A reaction with nonzero propensity is applicable, and firing an applicable reaction whose products differ from its reactants changes the counts.
2 Population protocols
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.
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})\).
There are \(n(n-1)\) ordered pairs of distinct agents, \(2 x_A x_B\) of them with species \(\{ A, B\} \) for \(A \ne B\), and \(x_A(x_A - 1)\) with species \(\{ A, A\} \).
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.
Average over the uniform reaction and apply the key identity to each reaction.
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.
Conditioned on reacting, the interaction fires \(r\) with probability proportional to \(a_r(x)\) by the key identity, which is the jump chain; from a configuration where no pair can react both sides stay put.
3 Approximate majority
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).
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.
Instances of the general results, with \(a_0(x) = k D\).
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.
Off the diagonal, the interaction moves as the network’s jump chain with the probability that the drawn pair reacts; if no pair can react, both kernels stay put.
4 Stable computation
This section and the two following ones formalize the easy direction of the characterization of stably computable predicates of Angluin, Aspnes, Diamadi, Fischer and Peralta, Computation in networks of passively mobile finite-state sensors (Distributed Computing 18, 2006). Their Lemma 5 needs a minor correction for a population of a single agent: no encounter happens, and if a lone agent keeps its state, its output stays \(0\) even when the predicate holds. The protocols formalized here start each agent with its single-agent output and are correct for every \(n\ge 1\) (details).
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.
A protocol stably computes at most one predicate on nonzero count vectors.
From the initial configuration of a population with the given counts, reach an output-stable configuration for the first predicate and then one for the second: they agree.
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.
Parallel composition: states are pairs, both components make their own transition in every encounter, and the output of \((p_1, p_2)\) is \(\xi (O_1 p_1, O_2 p_2)\).
5 Semilinear predicates
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.
Each agent holds a leader bit, an output bit and a count in \([-s, s]\), starting from \(a_i\); an encounter involving a leader merges the leaders into the initiator, which takes as much of the sum of the two counts as fits in \([-s, s]\), and both agents set their output to whether the initiator’s count is below \(c\). Unlike the original protocol, an input starts with output bit \([a_i {\lt} c]\), which is needed for a population of one agent. The second form is the negation.
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 same leader protocol with counts in \(\mathbb {Z}/m\): the initiator takes the sum of the two counts and the responder gets \(0\).
The Boolean combinations of threshold and remainder predicates.
The truth set of every such predicate is a semilinear set of count vectors, and every such predicate is stably computable.
Induction on the Boolean combination, with the two preceding theorems and Boolean closure; for the first part, semilinear sets are closed under complement, intersection and union.
6 From protocols to networks
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)\).
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.
Encounters change counts exactly by the corresponding reaction. Tagging the input states keeps the input map injective and provides a transition that changes the multiset of states.
7 Majority on graphs with very small local memory (CRN-4)
This section formalizes Theorems 1, 2 and 4 of Mertzios, Nikoletseas, Raptopoulos and Spirakis, Determining majority in networks with local interactions and very small local memory (ICALP 2014, arXiv:1404.7671, whose numbering we use; Distributed Computing 30, 2017): population protocols run on a connected interaction graph, and two agents interact only along an edge. The 3-state protocol is that of Angluin, Aspnes and Eisenstat (Distributed Computing 21, 2008). Graphs are undirected. The proofs of Theorems 1, 2 and 4 need minor corrections: in Theorem 1 the type of two agents and one set index are corrected; in Theorem 2 ambassadors of the same color can block each other, which a closest pair of opposite ambassadors avoids; in Theorem 4 the monotonicity step is stated without proof (it follows from a monotone coupling), and the bound \(1/2\) also needs absorption with probability \(1\) (details).
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.
On the complete graph these notions are those of Definition 14: stable computation on the complete graphs of all nonempty populations, with the trivial domain, is stable computation.
Every ordered pair of distinct agents is an oriented edge of the complete graph.
Reachability transfers along an injective map of agents that preserves edges, the other agents being frozen.
Induction on reachability: an encounter along \((u, v)\) is simulated along \((f(u), f(v))\).
With two input types, red and green, majority is true if red has more agents than green, and the domain excludes ties.
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.
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.
Count the two agents of an encounter, over the \(16\) entries of the table.
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.
Take a red ambassador and a closest green one. The red ambassador walks along a shortest path, moving onto vertices without ambassador and handing over to red ambassadors it meets, until it meets the green one (strong induction on the distance). Spreading is similar, by induction on the distance to a vertex of the other color and then on the number of such vertices.
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.
From every reachable configuration, annihilate pairs until only ambassadors of the majority color remain (there is one by the invariant), then spread that color. Configurations without ambassadors are frozen.
No protocol with at most \(3\) states stably computes majority, ties excluded, on the complete graphs of all nonempty populations, hence on all connected graphs. With Theorem 30, \(4\) is the minimal number of states.
A single agent never interacts, so both outputs occur, and one output \(b\) has a single state \(q_1\). On \(3\) agents, the inputs \((b, b, \lnot b)\) and \((b, b, b)\) both reach the configuration in which every agent is in \(q_1\). Adding two agents of input \(\lnot b\) and running the same encounters on the first three agents, inputs with majority \(\lnot b\) and \(b\) reach a common configuration, a contradiction.
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\).
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.
Run two ordered configurations with the same oriented edges; they stay ordered.
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.
Hall’s theorem, with Hall’s condition by double counting.
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.
For each \(m\)-set \(S\), the configuration with \(X\) exactly on \(A_S\) lies below the one with \(X\) exactly on \(S\), which is the swap of the placement with \(Y\) on \(S\). By monotonicity and symmetry, the minority wins from the first with probability at most the probability that the majority wins from the placement on \(S\). The first configuration is the placement on the \(m\)-set \(A_S^c\), and \(S \mapsto A_S^c\) is a bijection of the \(m\)-sets, so averaging over \(S\) gives the inequality (eqs. (18) to (23)).
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\).
An initiator \(s \ne B\) activated twice on the same responder makes it \(s\), so an opinion present spreads to all agents along the edges of a connected graph, and all-blank is never reached. Absorption in a finite chain follows, and the two convergence probabilities sum to \(1\).
8 Deterministic exact majority and plurality (CRN-5)
This section formalizes Theorems 3, 6 and 7 of Gąsieniec, Hamilton, Martin, Spirakis and Stachowiak, Deterministic population protocols for exact majority and plurality (OPODIS 2016, LIPIcs 70, paper 14). Colours are \(k\)-bit labels, so \(C \le 2^k\) colours need \(O(k)\) bits of memory. Fig. 4 of the paper needs a minor correction: one entry of its table breaks Invariant 2, and the rules of the text are used. The final argument of Section 3 needs a minor correction: it uses, in the tie case, that every group keeps a strong state, an invariant the paper does not state, which is added and proved. Section 5.2, which should inform all agents whether the most frequent colour is unique, needs a major correction and is not formalized: on the colours \(1, 1, -1\) its bit never stabilizes, in any execution (a repaired rule passes exhaustive checks on small populations). Theorem 7 is formalized as the protocol of Section 5.1 computes it: every agent learns whether its own colour is the plurality colour, not the winner’s label (details).
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.
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\).
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.
Check the encounters (by computation over the \(36\) pairs); while weights of both signs are present, bring two of them together, which decreases \(R\).
The static protocol stably computes \(\operatorname {sign}(\# 1 - \# (-1))\): all agents eventually and forever output \(1\), \(-1\), or \(0\) for a tie.
Once \(R = |S|\), every weight is \(0\) or \(s = \operatorname {sign} S\) and a strong agent \([s]\) exists (for \(s = 0\), a strong state is never lost). It recruits every agent into the states of output \(s\), a set closed under the transitions.
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.
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.
Encounter by encounter (by computation over the finite state space); a colour change moves the weight by the change of colour and makes the state strong.
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))\).
After Lemma 5, every nonzero weight in a group has the sign \(s\) of the group’s colour sum, and a strong agent of weight sign \(s\) exists in the group (the third invariant gives it in the tie case). It recruits the group into the states of output \(s\).
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.
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.
An encounter is an encounter of the dynamic protocol inside a group followed by two colour changes. Once \(D\) has stabilized, the colours are fixed and Theorem 45 applies in every group.
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.
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.
The \(k\) copies stabilize on the majority bits one at a time. Then the colour of an agent is \(1\) exactly when its label consists of the majority bits, so the eventual colour sum is positive if and only if that label is held by more than half of the agents, and the composition theorem applies with a single group.
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.
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 colour sum of the group of \(p\) is the difference of the counts of the two group winners, and ties go to the larger label.
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.
Induction on the levels: level \(m\) stably marks every agent with whether its label wins its group of prefix length \(k - m\), by the composition theorem and the duel lemma.