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\).
4 Stable computation
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.