Time-Space Trade-offs in Molecular Computation

Population protocols are a popular model of distributed computing, in which randomly-interacting agents with little computational power cooperate to jointly perform computational tasks. Inspired by developments in molecular computation, and in particular DNA computing, recent algorithmic work has focused on the complexity of solving simple yet fundamental tasks in the population model, such as leader election (which requires convergence to a single agent in a special"leader"state), and majority (in which agents must converge to a decision as to which of two possible initial states had higher initial count). Known results point towards an inherent trade-off between the time complexity of such algorithms, and the space complexity, i.e. size of the memory available to each agent. In this paper, we explore this trade-off and provide new upper and lower bounds for majority and leader election. First, we prove a unified lower bound, which relates the space available per node with the time complexity achievable by a protocol: for instance, our result implies that any protocol solving either of these tasks for $n$ agents using $O( \log \log n )$ states must take $\Omega( n / \rm{polylog} n )$ expected time. This is the first result to characterize time complexity for protocols which employ super-constant number of states per node, and proves that fast, poly-logarithmic running times require protocols to have relatively large space costs. On the positive side, we give algorithms showing that fast, poly-logarithmic convergence time can be achieved using $O( \log^2 n )$ space per node, in the case of both tasks. Overall, our results highlight a time complexity separation between $O(\log \log n)$ and $\Theta( \log^2 n )$ state space size for both majority and leader election in population protocols, and introduce new techniques, which should be applicable more broadly.


Introduction
Population protocols [AAD + 06] are a model of distributed computing in which agents with little computational power and no control over the interaction schedule cooperate to collectively perform computational tasks. While initially introduced to model animal populations [AAD + 06], they have proved a useful abstraction for wireless sensor networks [PVV09,DV12], chemical reaction networks [CCDS14], and gene regulatory networks [BB04]. A parallel line of applied research has shown that population protocols can be implemented at the level of DNA molecules [CDS + 13], and that they are equivalent to computational tasks solved by living cells in order to function correctly [CCN12].
Specifically, a population protocol consists of a set of n finite-state agents, interacting in pairs, where each interaction may update the local state of both participants. The protocol starts in a valid initial configuration, and defines the outcomes of pairwise interactions. The goal is to have all agents converge to some state, representing the output of the computation, which satisfies some predicate over the initial state of the system. For example, one fundamental task is majority (consensus) [AAE08b, PVV09,DV12], in which agents start in one of two input states A and B, and must converge on a decision as to which state has a higher initial count. A complementary fundamental task is leader election [AAE08a, AG15, DS15], which requires the system to converge to final states in which a single agent is in a special leader state.
The set of interactions occurring in each step is usually assumed to be decided by a probabilistic scheduler, which picks the next pair to interact uniformly at random. One complexity measure is parallel time, defined as the number of pairwise interactions until convergence, divided by n, the number of agents. Another is space complexity, defined as the number of distinct states that an agent can represent internally.
There has been considerable interest in the complexity of fundamental tasks such as leader election and consensus in the population model. In particular, a progression of deep technical results [Dot14,CCDS14] has culminated in showing that leader election in sublinear time is impossible for protocols which are restricted to a constant number of states per node [DS15]. At the same time, it is now known that leader election can be solved in O(log 3 n) time via a protocol requiring O(log 3 n) states per node [AG15]. For the majority task, the space-time complexity gap is much wider: sublinear time is impossible for protocols restricted to having at most four states per node [AGV15], but there exists a poly-logarithmic time protocol which requires a number of states per node that is linear in n [AGV15].
These results hint towards a trade-off between the running time of a population protocol and the space, or number of states, available at each agent. This relation is all the more important since time efficiency is critical in practical implementations, while technical constraints limit the number of states currently implementable in a molecule [CDS + 13]. (One such technical constraint is the possibility of leaks, i.e. spurious creation of states following an interaction [TWS15]. In DNA implementations, the more states a protocol implements, the higher the likelihood of a leak, and the higher the probability of divergence.) However, the characteristics of the time-space trade-off in population protocols are currently an open question. Contribution: In this paper, we take a step towards answering this question. First, we exhibit a general trade-off between the number of states available to a population protocol and its time complexity, which characterizes which deterministic predicates can be computed efficiently with limited space. Further, we give new and improved algorithms for majority and leader election, tight within poly-logarithmic factors. Lower Bounds: When applied to majority, our lower bound proves that there exist constants c ∈ (0, 1) and K ≥ 1 such that any protocol using λ n ≤ c log log n states must take Ω(n/(K λn + n) 2 )) time, where n is the difference between the initial counts of the two competing states. For example, any protocol using constant states and supporting a constant initial difference necessarily takes linear time.
For leader election, we show that there exist constants c ∈ (0, 1) and K ≥ 1 such that any protocol using λ n ≤ c log log n states and electing at most (n) leaders, requires Ω(n/(K λn · (n) 2 )) expected time. Specifically, any protocol electing one leader using ≤ c log log n states requires Ω(n/polylog n) time. Algorithms: On the positive side, we give new poly-logarithmic-time algorithms for majority and leader election which use O(log 2 n) space. Our majority algorithm, called Split-Join, runs in O(log 3 n) time with high probability, and uses O(log 2 n) states per node. The only previosly known algorithms to achieve sublinear time required Θ(n) states per node [AGV15], or exponentially many states per node [BFK + 16]. Further, we give a new leader election algorithm called Lottery-Election, which uses O(log 2 n) states, and converges in O(log 5.3 n log log n) parallel time in expectation and O(log 6.3 n) parallel time with high probability. This reduces the state space size by a logarithmic factor over the best known algorithm [AG15], at the cost of a poly-logarithmic running time increase. Techniques: The core of the lower bound is a two-step argument. First, we prove that a hypothetical algorithm which would converge faster than allowed by the lower bound may reach "stable" configurations 1 in which certain low-count states can be "erased," i.e., may disappear completely following a sequence of reactions. In the second step, we engineer examples where these low-count states are exactly the set of all possible leaders (in the case of leader election protocols), or a set of nodes whose state may sway the outcome of the majority computation (in the case of consensus). This implies a contradiction with the correctness of the computation. Technically, our argument employs the method of bounded differences to obtain a stronger version of the main density theorem of [Dot14], and develops a new technical characterization of the stable states which can be reached by a protocol, which does not require constant bounds on state space size, generalizing upon [DS15]. The argument provides a unified analysis: the bounds for each task in turn are corollaries of the main theorem characterizing the existence of certain stable configurations.
On the algorithmic side, we introduce a new synthetic coin technique, which allows nodes to generate almost-uniform local coins within a constant number of interactions, by exploiting the randomness in the scheduler, and in particular the properties of random walks on the hypercube. Synthetic coins are useful in both our protocols, for instance by allowing nodes to estimate the total number of agents in the system, and may be of independent interest as a way of generating randomness in a constrained setting.
The Split-Join majority protocol starts from the following idea: nodes can encode their output opinions and their relative strength as integer values: the value is positive if the node supports a majority of A, and negative if the node supports a majority of B. The higher the absolute value, the higher the "confidence" in the corresponding outcome. Whenever two nodes meet, they average their values, rounding to integers. This template has been used successfully in [AGV15] to achieve consensus in poly-logarithmic time, but doing so requires a state space of size at least linear n, as all values between 1 and n may need to be represented. Here we introduce a new quantized averaging technique, by which nodes represent their output estimates by encoding them as powers of two. Again, opinions are averaged on each interaction. We prove that our quantization preserves correctness, and allows for fast (poly-logarithmic) convergence, while reducing the size of the state space almost exponentially.
The Lottery-Election protocol starts from the basic mechanism where every agent is a potential leader, and whenever two leaders interact, one drops out of contention. 2 We boost this algorithm via two ideas: the first is to employ synthetic coins to "seed" potential leaders randomly, reducing the number of leaders at an accelerated rate; the second is a propagation mechanism similar to that of [AG15], by which nodes who drop out of contention assume the identity of their victor, causing nodes still in contention but with lower seeding to drop out. Overview: Our lower bound can be seen as bad news for algorithm designers, since it show that convergence is slow even if the protocol implements a super-constant number of states per node. On the positive side, the achievable convergence time improves quickly as the size of the state space nears the logarithmic threshold: in particular, fast, poly-logarithmic time can be achieved using poly-logarithmic space.
It is interesting to note that previous work by Chatzigiannakis et al. [MNRS14] identified Θ(log log n) as a space complexity threshold in terms of the computational power of population protocols. In particular, their results show that variants of such systems in which nodes are limited to o(log log n) space per node are limited to only computing semilinear predicates, whereas O(log n) space is sufficient to compute general symmetric predicates. By contrast, we show a complexity separation between algorithms which use O(log log n) space per node, and algorithms employing Ω(log n) space per node.

Preliminaries
Population Protocols: A population protocol is a set of n ≥ 2 agents, or nodes, each executing as a deterministic state machine with states from a finite set Λ n , whose size might depend on n. The agents do not have identifiers, so two agents in the same state are identical and interchangeable. Thus, we can represent any set of agents simply by the counts of agents in every state, which we call a configuration. Formally, a configuration c is a function c : Λ n → N, where c(s) represents the number of agents in state s in configuration c. We let |c| stand for the sum, over all states s ∈ Λ n , of c(s), which is the same as the total number of agents in configuration c. For instance, if c is a configuration of all agents in the system, then c describes the global state of the system, and |c| = n.
Further, we define the set I n of all allowed initial configurations of the protocol for n agents, a finite set of output symbols O, a transition function δ n : Λ n × Λ n → Λ n × Λ n , and an output function γ n : Λ n → O. The system starts in one of the initial configurations i n ∈ I n (clearly, |i n | = n), and each agent keeps updating its local state following interactions with other agents, according to the transition function δ n . The execution proceeds in steps, where in each step a new pair of agents is selected uniformly at random from the set of all pairs. Each of the two chosen agents updates its state according to the function δ n .
A population protocol P will be a sequence of protocols P 2 , P 3 , . . . , where for each n ≥ 2 we have P n = (Λ n , I n , δ n , γ n ), defining the initial configurations, protocol states, transitions and output mapping, respectively, for n agents. We say that a protocol is monotonic if, for all i ≥ 1, (1) the number of states cannot decrease for higher node count i, i.e., |Λ i | ≤ |Λ i+1 |, and (2) if the state counts are the same, then the protocol is the same, i.e. if |Λ i | = |Λ j |, then Λ i = Λ j , I i = I j , δ i = δ j and γ i = γ j .
We say that a monotonic population protocol P is input-additive, if for all i n ∈ I n with |Λ n | = |Λ 2n | (which by monotonicity implies P n = P 2n ), it holds that i n + i n ∈ I 2n , i.e. doubling the number of agents in each state still leads to a valid initial configuration in a system of 2n agents.
A configuration c is reachable from a configuration c, denoted c =⇒ c , if there exists a sequence of consecutive steps (interactions from δ n between pairs of agents) leading from c to c . If the transition sequence is p, we will also write c =⇒ p c . We call a configuration c the sum of configurations c 1 and c 2 and write c = c 1 + c 2 , iff c(s) = c 1 (s) + c 2 (s) for all states s ∈ Λ n . Leader Election: Fix an n ≥ 2. In the leader election problem, all agents start in the same initial state A n , i.e. I n = {i n } with i n (A n ) = n. The output set is O = {Win, Lose}.
We say that a configuration c has a single leader if there exists some state s ∈ Λ n with γ n (s) = Win and c(s) = 1, such that for any other state s = s, c(s ) > 0 implies γ n (s ) = Lose. A population protocol P n solves leader election within r steps with probability 1 − φ, if, with probability 1 − φ, any configuration c reachable from i n by the protocol within ≥ r steps has a single leader. The Majority Problem: Fix an n ≥ 2. In the majority problem, we have two initial states A n , B n ∈ Λ n , and I n consists of all configurations where each of the n agents is either in A n or B n . The output set is O = {Win A , Win B }. Given an initial configuration i n ∈ I n let a = i n (A n ) and b = i n (B n ) be the count of the two initial states, and let n = |a − b| denote the initial relative advantage of the majority state.
We say that a configuration c correctly outputs the majority decision for i n , when for any state s ∈ Λ n , if a > b then c(s) > 0 implies γ n (s) = Win A , and if b > a then c(s) > 0 implies γ n (s) = Win B . (The output in case of an initial tie is arbitrary.) A population protocol P n solves the majority problem from i n within steps with probability 1 − φ, if for any configuration c reachable from i n by the protocol with ≥ steps, with probability 1 − φ, the protocol correctly outputs the majority for i n . In this paper we consider the exact majority task, as opposed to approximate majority [AAE08b], which allows the wrong output with some probability.
Finally, a population protocol P solves a task if, for every n ≥ 2, the protocol instantiation P n solves the task. The complexity measures for a protocol (defined below), are functions of n. Stabilization: A configuration c of n agents has a stable leader, if for all c reachable from c, it holds that c has a single leader. Analogously, a configuration c has a stable correct majority decision for i n , if for all c with c =⇒ c , c correctly outputs the majority decision for i n . We say that a protocol stabilizes when it reaches such a stable output configuration. Complexity measures: The above setup considers sequential interactions; however, interactions between pairs of distinct agents are independent, and are usually considered as occurring in parallel. It is customary to define one unit of parallel time as n consecutive steps of the protocol. We are interested in the expected parallel time for a population protocol to stabilize, i.e. the total number of (sequential) interactions from the initial configuration required to reach a configuration with a stable leader or with a stable correct majority decision, divided by n. We also refer to this quantity as the convergence time. If the expected time is finite, then we say that population protocol stably elects a leader (or stably computes majority decision). The space complexity of a protocol is the number of states in the protocol with respect to n, i.e. |Λ n |.

Lower Bound
Our definition of population protocols allows the protocol to arbitrarily change its structure as the number of states changes. This generality strengthens the lower bound, and to our knowledge, the definition covers all known population protocols. Technical machinery: We now lay the groundwork for our main argument by proving a set of technical lemmas. In the following, we assume n to be fixed; Λ n is the set of all states of the protocol. Let S be an arbitrary set of states. Abusing notation, we denote by δ n (S, S) the set of all states which can be generated by transitions between states in S. Then, we let S 0 be the set of states in the initial configurations of the protocol and for all integers k ≥ 1, we define inductively the set of states S k = S k−1 ∪ δ n (S k−1 , S k−1 ). Simply put, S k is the set of all states which can be generated by the protocol after k steps.
Assume without loss of generality that all states in Λ n actually occur in some configurations reachable by the protocol P n from some initial configuration. Then, it holds that S |Λn|−1 = S |Λn| = . . . , and S |Λn|−1 = Λ n . We say that a configuration c is X-rich if all states that are present have count have count ≥ X. A configuration is dense if it is n/M -rich, for some constant M > 1. We call an initial configuration fully dense, if it is dense and contains (at least n/M ) agents in each of the states from S 0 . We now prove the following statement, which generalizes the main result of [Dot14] to super-constant state counts.
Lemma A.1. For all population protocols A using |Λ n | ≤ 1/2 log log n states, starting in a fully dense initial configuration, with probability ≥ 1 − (1/n) 0.99 , there exists a step j such that the configuration reached after j steps is n 0.99 -rich.
Fix a function f : N → R + . Fix a configuration c, and states r 1 and r 2 in c. A transition α : (r 1 , . This bottleneck transition implies that the probability of a transition (r 1 , r 2 ) → (z 1 , z 2 ) is bounded. Hence, proving that transition sequences from initial configuration to final configurations contain a bottleneck implies a lower bound on the convergence time.
Conversely, the next lemma shows that, if a protocol converges fast, then it must be possible to converge using a transition sequence which does not contain any bottleneck.
Lemma A.3. Let P be a population protocol with |Λ n | ≤ 1/2 log log n states, and let D n ⊆ I n be a nonempty set of fully dense initial configurations. Fix a function f . Assume that for sufficiently large n, P stabilizes in expected time o n f (n)|Λn| 2 from all i n ∈ D n . Then, for all sufficiently large m ∈ N there is a configuration x m with m agents, reachable from some i ∈ D m and a transition sequence p m , such that: 1. x m (s) ≥ m 0.99 for all s ∈ Λ m , 2. x m =⇒ pm y m , where y m is a stable output configuration, and 3. p m has no f -bottleneck.
Hence, fast convergence from a sufficiently rich configuration requires the existence of a bottleneck-free transition sequence. The next transition ordering lemma, due to [CCDS14], proves a property of such a transition sequence: there exists an order over all states whose counts decrease more than some set threshold such that, for each of these states d j , the sequence contains at least a certain number of a specific transition that consumes d j , but does not consume or produce any states d 1 , . . . , d j−1 that are earlier in the ordering.
Lemma A.4. Fix b ∈ N, and let B = |Λ n | 2 · b + |Λ n | · b. Given configurations x, y : Λ n → N in a system of n agents, such that for all states s ∈ Λ n we have x(s) ≥ B 2 and x =⇒ q y via a transition sequence q without a B 2 -bottleneck. Define ∆ = {d ∈ Λ n | y(d) ≤ b} to be the set of states whose count in configuration y is at most b. Then there is an order ∆ = {d 1 , d 2 , . . . , d k }, such that, for all j ∈ {1, . . . , k}, there is a transition α j of the form (d j , s j ) → (o j , o j ) with s j , o j , o j ∈ {d 1 , . . . , d j }, and α j occurs at least b times in q.
The Lower Bound Argument: Given a population protocol P n , a configuration c : Λ n → N and a function g : N → N + , we define the sets Γ g (c) = {s ∈ Λ n | c(s) > g(|c|)} and ∆ g (c) = {s ∈ Λ n | c(s) ≤ g(|c|)}. Intuitively, Γ g (c) contains states above a certain count, while ∆ g (c) contains state below that count. Notice that Γ g (c) = Λ n − ∆ g (c).
The proof strategy is to first show that if a protocol converges "too fast," then it can also reach configurations where all agents are in states in Γ g (c). Recall that a configuration c is defined as a function Λ n → N. Let S ⊆ Λ n be some subset of states such that all agents in configuration c are in states from S, formally, {s ∈ Λ n | c(s) > 0} ⊆ S. For notational convenience, we will write c >0 ⊆ S to mean the same.
Suppose P stabilizes in o n (6 |Λn| ·|Λn| 3 ·g(n)) 2 time from any initial configuration, and that it has fully dense initial configurations for all sufficiently large n. Then, for infinitely many m with |Λ m | = . . . = |Λ 3m |, we can find an initial configuration of 2m agents i ∈ I 2m and stable output configuration y of m agents, such that for any configuration u that satisfies a requirement below, i + u =⇒ z holds, where z >0 ⊆ Γ g (y).
The requirement on configuration u is that it contains between 0 and m agents, u >0 ⊆ ∆ g (y) (all agents in u are in states from ∆ g (y)), and that y(s) + u(s) ≤ g(m) for all states s ∈ ∆ g (y).
The theorem statement implies that the protocol stabilizes in o n f (n)|Λn| 2 time. By Lemma A.3, for all sufficiently large m we can find configurations of m agents i m , x m , y : Λ m → N, such that: • i m ∈ I m is a fully dense initial configuration of m agents.
• i m =⇒ x m =⇒ pm y, where y is a stable final configuration, as desired, and the transition sequence p m does not contain an f -bottleneck (i.e. a (b 2 ) 2 -bottleneck). • ∀s ∈ Λ m : x m (s) ≥ b 2 (m). (Here, we use the assumption on the function g.) Moreover, because |Λ n | ≤ 1/2 log log n for sufficiently large n, for infinitely many m it also additionally holds that |Λ m | = |Λ m+1 | = . . . = |Λ 3m | (otherwise |Λ n | would grow at least logarithmically in n). This, due to monotonicity implies that population protocols P m , P m+1 , . . . , P 3m are all the same.
Consider any such m. Then, we can invoke Lemma A.4 with x m , y, transition sequence p m and parameter b = b(m). The definition of ∆ in the lemma statement matches ∆ b (y), and b 2 matches b 2 (m). Thus, we get an ordering of states ∆ b (y) = {d 1 , d 2 , . . . , d k } and a corresponding sequence of transitions α 1 , α 2 , . . . , α k , where each α j is of the form (d j , s j ) → (o j , o j ) with s j , o j , o j ∈ {d 1 , d 2 , . . . , d j }. Finally, each transition α j occurs at least b(m) = (6 |Λm| + 2 |Λm| ) · g(m) times in p m .
We will now perform a set of transformations on the transition sequence p m , called surgeries, with the goal of converging to a desired type of configuration. The next two claims specify these transformations, which are similar to the surgeries used in [DS15], but with some key differences due to configuration u and the new general definitions of Γ and ∆. The proofs are provided in the appendix. Configuration u is defined as in the theorem statement. For brevity, we use Γ g = Γ g (y), ∆ g = ∆ g (y), Γ b = Γ b (y) and ∆ b = ∆ b (y).
Claim A.5. There exist configurations e : Λ m → N and z with z >0 ⊆ Γ g , such that e + u + x m =⇒ z . Moreover, we have an upper bound on the counts of states in e: ∀s ∈ Λ m : e(s) ≤ 2 |Λm| · g(m).
The configuration e + u + x m has at most 2 |Λm| · g(m) · |Λ m | + g(m) + m agents, which is less than 3m for sufficiently large m. The state transitions used here and everywhere below are from δ m = . . . = δ 3m .
For any configuration e : Λ m → N, let e ∆ be its projection onto ∆, i.e. a configuration consisting of only the agents from e in states ∆. We can define e Γ analogously. By definition, e Γ = e − e ∆ .
Let our initial configuration i be i m +i m , which because i m is fully dense and because of input-additivity, must also be a fully dense initial configuration from I 2m . Trivially, i =⇒ x m + x m . Let us apply Claim A.6 with e as defined in Claim A.5, but use one x m instead of p. This is possible because ∀s ∈ Λ m : The configuration w − e Γg is well-defined because both w and e Γg contain agents in states in Γ g , with each count in w being larger or equal to the respective count in e Γg , by the bounds from the claims.
Finally, by Claim A.5, we have u + x m + e + (w − e Γg ) =⇒ z + (w − e Γg ). We denote the resulting configuration (with all agents in states in Γ g ) by z, and have i =⇒ z, as desired.
The following lemma is a technical tool that critically relies on our definitions of Γ and ∆.
Lemma A.7. Consider a population protocol in a system with any fixed number of agents n, and an arbitrary fixed function h : N → N + such that h(n) ≥ 2 |Λn| . Let ξ(n) = 2 |Λn| . For all configurations c, c : Λ n → N, such that c >0 ⊆ Γ h (c) ⊆ Γ ξ (c ), any state producible from c is also producible from c . Formally, for any state s ∈ Λ n , c =⇒ y with y(s) > 0 implies c =⇒ y with y (s) > 0. Now we can prove the lower bounds on majority and leader election.
Corollary 3.2. Any monotonic population protocol with |Λ n | ≤ 1/2 log log n states for all sufficiently large number of agents n that stably elects at least one and at most (n) leaders, must take Ω n 144 |Λn| ·|Λn| 6 · (n) 2 expected parallel time to convergence.
Proof. We set g(n) = 2 |Λn| · (n). In the initial configurations for leader election all agents are in the same starting state. Hence, all initial configurations are fully dense, and all monotonic population protocols for leader election have to be input-additive.
Assume for contradiction that the protocol converges in parallel time o n 144 |Λn| ·|Λn| 6 · (n) 2 . For all n, I n contains the only initial fully dense configuration with n agents in the same initial state. Using Theorem 3.1 and setting u to be a configuration of zero agents, we can find infinitely many configurations i and z of 2m agents, such that (1) i =⇒ z, (2) i ∈ I 2m , (3) |Λ m | = |Λ 2m | and by monotonicity, the same protocol is used for all number of agents between m and 2m, (4) z >0 ⊆ Γ g (y), i.e. all agents in z are in states that each have counts of at least 2 |Λm| · (m) in some stable output configuration y (of |y| = m agents).
Because y is a stable output configuration of a protocol that elects at most (m) leaders, none of these states in Γ g (y) that are present in strictly larger counts (2 |Λm| · (m) > (m)) in y and z can be leader states (i.e. γ m = γ 2m maps these states to output Lose). Therefore, the configuration z does not contain a leader. This is not sufficient for a contradiction, because a leader election protocol may well pass through a leaderless configuration before converging to a stable configuration with at most (m) leaders. We prove below that any configuration reachable from z must also have zero leaders. This implies an infinite time of convergence from a valid initial configuration i (as i =⇒ z) and completes the proof by contradiction.
If we could reach a configuration from z with an agent in a leader state, then by Lemma A.7, from a configuration c that consists of 2 |Λm| agents in each of the states in Γ g (y), it is also possible to reach a configuration with a leader, let us say through transition sequence q. Recall that the configuration y contains at least 2 |Λm| · (m) agents in each of these states in Γ g (y), hence there exist disjoint configurations c 1 ⊆ y, c 2 ⊆ y, etc, . . . , c (m) ⊆ y contained in y and corresponding transition sequences q 1 , q 2 , . . . , q (m) , such that q j only affects agents in c j and leads one of the agents in c j to become a leader. Configuration y is a output configuration so it contains at least one leader agent already, which does not belong to any c j because as mentioned above, all agents in c j are in non-leader states. Therefore, it is possible to reach a configuration from y with (m) + 1 leaders via a transition sequence q 1 on the c 1 component of y, followed by q 2 on c 2 , etc, q (m) on c (m) , contradicting that y is a stable output configuration.
The proof of the majority lower bound follows similarly, and is deferred to the Appendix.
Corollary A.8. Any monotonic population protocol with |Λ n | ≤ 1/2 log log n states for all sufficiently large number of agents n that stably computes correct majority decision for initial configurations with majority advantage n, must take Ω n 36 |Λn| ·|Λn| 6 ·max(2 |Λn| , n) 2 expected parallel time to convergence.

Synthetic Coin Flips
The state transition rules in population protocols are deterministic, i.e. the interacting nodes do not have access to random coin flips. In this section, we introduce a general technique that extracts randomness from the schedule and after only constant parallel time, allows the interactions to rely on close-to-uniform synthetic coin flips. This turns out to be an useful gadget for designing efficient protocols.
Suppose that every node in the system has a boolean parameter coin, initialized with zero. This extra parameter can be maintained independently of the rest of the protocol, and only doubles the state space.
When agents x and y interact, they both flip the values of their coins. Formally, x .coin ← 1 − x.coin and y .coin ← 1 − y.coin, and the update rule is fully symmetric.
The nodes can use the coin value of the interaction partner as a random bit in a randomized algorithm. Clearly, these bits are not independent or uniform. However, we prove that with high probability the distribution of coin quickly becomes close to uniform and remains that way. We use the concentration properties of random walks on the hypercube, analyzed previously in various other contexts, e.g. [AR15]. We also note that a similar algorithm is used by Laurenti et al.
[LCK16] to generate randomness in chemical reaction networks, although they do not prove convergence bounds.
Theorem 4.1. Suppose k ≥ αn for a fixed constant α ≥ 2. Let X i be the number of ones in the system after i interactions. For all sufficiently large n, we have that Pr[|X k − n/2| ≥ n/2 4α ] ≤ 2 exp(−αn/8).
Proof. We label the nodes from 1 to n, and represent their coin values by a binary vector of size n. Suppose we knew a fixed vector v representing the coin values of the nodes after the interaction k − αn. For example, if k = αn, we know v is a zero vector, because of the way the algorithm is initialized. For 1 ≤ t ≤ αn, define by Y t the pair of nodes that are flipped during interaction k − αn + t. Then, X k is a deterministic function of Y 1 , . . . , Y αn , (whereby the function encodes the fixed starting vector v). Moreover, Y j are independent random variables and changing any one Y j only changes X k by at most 4. Hence, we can apply McDiarmid's inequality with X k = f v (Y 1 , . . . , Y αn ).
Claim 4.2 (McDiarmid's inequality). Let Y 1 , . . . , Y m be independent random variables and let X be their function X = f (Y 1 , . . . , Y m ), such that changing variable Y j only changes the function value by at most c j .
given that the coin values after interaction k − αn are fixed and represented by vector v. Fixing v also fixes the number of ones among coin values in the system at that moment, which we will denote by x, i.e. x = n j=1 v j = X k−αn . We then notice that the following claim holds, whose proof is deferred to the Appendix.
For each fixed v, we can apply McDiarmid inequality as above, and get an upper bound on the probability that X k (given the fixed v), diverges from the expectation by at most α √ n. But as we just established, for any v, the expectation we get in the bound will be at most n/2 4α+1 away from n/2. Combining these and using n/2 4α+1 ≥ α √ n for all sufficiently large n gives the desired bound.
Approximate Counting: Synthetic coins can be used to estimate the number of agents in the system, as follows. Each node executes the coin-flipping protocol, and counts the number of consecutive 1 flips it observes, until the first 0. Each agent records the number of consecutive 1 coin flips as its estimates. The agents then exchange their estimates, always adopting the maximum estimate. It is easy to prove that the nodes will eventually converge to a number which is a constant-factor approximation of log n, with high probability. This property is made precise in the proof of Lemma D.2.

The Lottery Leader Election Algorithm
Overview: We now present a leader election population protocol using O(log 2 n) states. The protocol is split conceptually into two stages: in the first lottery stage, each agent generates an individual payoff by flipping synthetic coins. In the second competition stage, each agent starts as a potential leader, and proceeds to compare a value associated with local state against that of each interaction partner. Of any two interacting agents, the one with "larger" value wins, and remains in contention, while the other drops out and becomes a minion. Importantly, a minion agent can no longer be a leader, but carries the value of its victor in future interactions. Thus, if an agent still in contention meets a minion with higher value, it will drop out and adopt the higher value. Similarly, a minion will always adopt the highest leader value it encounters. This minion-based propagation mechanism has been used previously, where the value corresponded to interaction counts [AG15]; here, we employ a more complex value function, which requires less states to store. We now present the algorithm in detail. Initially, all nodes start in the same state, which is determined by seven parameters: coin, mode, payoff , level , counter , phase and ones. The coin parameter stores the synthetic coin value; it is binary, initially 0. The agent can be in one of four modes: seeding (preparing the random coin), lottery (generating the payoff value), tournament (competing), or minion (out of contention).
We fix a parameter m such that m ≥ (10 log n) 2 . The protocol will use O(m) states per node. Seeding Mode: All agents start in seeding mode, with payoff and level values 0, and counter value 4. The goal of the four-interaction seeding mode is for the synthetic coin implemented by the coin parameter to mix well, generating values which are close to uniform random. In the first four interactions, each agent simply decreases its counter value. Once this counter reaches 0, the agent moves to lottery mode. By the properties of synthetic coins, when agents finish seeding, they hold 0 or 1 values in roughly equal proportion. Lottery Mode: In lottery mode, an agent starts counting in its own payoff the number of consecutive interactions until observing 0 as the coin value of an interaction partner, by incrementing payoff upon observing 1 coins. When the agent first meets a 0, or if the agent reaches the maximum possible value that payoff can hold, set to √ m, the agent x finalizes its payoff , and changes its mode to tournament. Tournament Mode: The goal of tournament mode is two-fold: to force agents to compete (by comparing states), and to generate additional tie-breaking random values (via the level variable).
Agents start with level = 0 and repeatedly attempt to increase their level. Each agent x keeps track of phases, consisting of Θ(log payoff ) consecutive interactions. In each phase, if all coin values of interaction partners are 1, then the x.level is incremented; otherwise, it stays the same. An agent which reaches the maximum possible level , set at √ m/ log m, remains in tournament mode, but stops increasing its level. Phases can be implemented by the phase parameter used as a counter, and a boolean ones parameter. phase starts with 0, and is incremented every interaction until it is reset to 0 when the phase ends. ones is set to true at the beginning of each phase and becomes false is coin value 0 is encountered. As mentioned above, the phase consists of Θ(log payoff ) interactions, and the exact function will be provided later.
When two agents x and y in tournament mode meet, they compare (x.payoff , x.level , x.coin) and (y.payoff , y.level , y.coin). If the former is larger, then agent x eliminates agent y from the tournament, and vice versa. Practically, agent y sets its mode to minion, and adopts the payoff and level values of the other agent. Note that agents with higher lottery payoff always have priority; if both payoff and level are equal, the coin value is used as a tie-breaker. Minion Mode: An agent in minion mode keeps a record of the maximum .payoff , .level pair ever encountered in any interaction in its own payoff and level parameters. If x.mode = minion and y.mode = tournament, and (x.payoff , x.level ) > (y.payoff , y.level ), then the agent in state y will be eliminated from contention, and turned into a minion. Intuitively, minions help leaders with high payoffs and levels to eliminate other contenders by spreading information. Importantly, minions do not use the coin value as a tie-breaker (as this could lead to a leader eliminating itself via a cycle of interactions). Analysis Overview: The main intuition is that one agent with the highest lottery payoff eventually becomes the leader. This is an agent that manages to reach a high level, and turns other competitors into its minions, that further propagate the information about the highest payoff and level through the system.
Only nodes with mode = minion are non-leaders, and once a node becomes a minion it remains a minion. Therefore, we first prove in Lemma D.1 that not all nodes can become minions, and if there are n − 1 minions in the system, then there is a stable leader. The proofs are provided in the appendix.
The number of possible states of an agent can be determined by multiplying the maximum different values of state parameters, giving O(1) · √ m · √ m log m · O(log m) = O(m) as desired. Next, we prove in Lemma D.2 that with probability at least 1 − O(1)/n 3 , after O(n log n) interactions, all agents will be in the competition stage, that is, either in tournament or minion mode, with maximum payoff at least log n/2 and at most 9 log n, and at most 5 log n agents will have this maximum payoff .
We set the phase size of an agent with payoff = p to 4.2(log p + 1). We then show in Lemma D.3 that with probability at least 1 − O(1)/n 3 , only one contender reaches level = 3 log n/ log log n, and it takes at most O(n log 5.3 log log n) interactions for a new level to be reached up to .
The above claims imply that with high probability (at least 1 − O(1)/n 3 ), the protocol elects a single leader within O(n log n) + O(n log 5.3 log log n) · = O(n log 6.3 n) interactions, that is, O(log 6.3 n) parallel time. Finally, Lemma D.4 gives a O(log 5.3 n log log n) bound on expected parallel time until convergence.

The Split-Join Majority Algorithm
Overview: In this section, we present an algorithm for exact majority using O(log 2 n) states per node. The main idea behind the algorithm is that each node state corresponds to an integer value: the sign of the value corresponds to the node's opinion about the majority state-by convention, A is positive, and B is negative. To minimize the state space, we will devise a special representation for the integer values, where not all integers will be representable. Whenever two nodes meet, they modify their respective values following a sequence of simple operations. The intuition is that, on each interaction, nodes average their corresponding values. Averaging ensures that the sign of the sum over all values in the system never changes, while, initially, this sign corresponds to the sign of the majority value. Thus, the crux of the analysis will be to show that all nodes converge to values of the same sign, and do so quickly.
States: We now describe the algorithm in detail. Each node state corresponds to a pair of integers x and y, represented by x, y , whereby both integers are powers of two from x, y ∈ {0, 1, 2, 2 2 , . . . , 2 log n }, where n is the number of nodes. The value of a state corresponding to a pair x, y is value( x, y ) = x − y.
Nodes start in one of two special states. By convention, nodes starting in state A have the initial pair 2 log n , 0 , and the nodes starting in state B have the initial pair 0, 2 log n . (Here, we assume that nodes have an estimate of n. This estimate can be obtained in logarithmic time using the approximate counter from Section 4.) We distinguish between two types of states: strong states represent non-zero values, and will always satisfy x = y and 2 min(x, y) = max(x, y). The weak states are represented as pairs 0, 0 + and 0, 0 − , corresponding to value 0, leaning towards A or B, respectively. We will refer to states and their corresponding value pairs interchangeably. The output function γ maps each state to the output based the sign of its value (treating 0, 0 + as positive and 0, 0 − as negative).
Interactions: The algorithm, specified in Figure 1, consists of a set of simple deterministic update rules for the node state, to be applied on every interaction. In the pseudocode, we make the distinction between pairs x, y , which correspond to states, and pairs [x, y] corresponding to tuples of integer values. The interaction rule between the states x 1 , y 1 and x 2 , y 2 of two interacting nodes is described by the function interact. The states after the interaction are x 1 , y 1 and x 2 , y 2 . All nodes start in the designated initial states and continue to interact according to the interact rule. If both interacting states are weak, nothing changes (line 24). Otherwise, three elementary reactions, cancel, join, and split are applied, in this order. Each reaction takes four values x 1 , y 1 , x 2 , y 2 and returns (possibly updated) values x 1 , y 1 , x 2 , y 2 .
The cancel reaction matches positive and negative powers of 2 from the two interaction partners. The join operation matches values of the same sign, attempting to create higher powers of two. The split reaction does the opposite, by breaking powers of two into smaller powers. Please see Figure 2 for an illustration. Before returning, the interact procedure normalizes the two states to satisfy some simple well-formedness conditions. Notice that all these operations preserve the sum of values corresponding to their inputs. Correctness and Convergence: The first observation is that the sum of values in the system is constant throughout the execution. By construction, the initial sum is of the majority sign; since the sum stays constant, the algorithm may not reach a state in which all nodes have an opinion corresponding to the initial minority. This guarantees correctness. The convergence bound follows by carefully tracking the maximum value in the system, and showing that minority values get cancelled out and switch sign quickly.
Theorem B.1. The Split-Join algorithm will never converge to the minority decision, and is guaranteed to converge to the majority decision within O(log 3 n) parallel time, w.h.p.

Conclusion
We have studied the trade-off between time and space complexity in population protocols, and showed that a super-constant state space is necessary to obtain fast, poly-logarithmic convergence time for both leader election and exact majority. On the positive side, we gave algorithms which achieve poly-logarithmic expected convergence time using O(log 2 n) states per node for both tasks. Our findings are not great news for practitioners, as even small constant state counts are currently difficult to implement [CDS + 13]. It is interesting to note how nature appears to have overcome this impossibility: algorithms solving majority at the cell level do so approximately, allowing for a positive probability of error, using small constant states per node and converging in poly-logarithmic time [AAE08b].
We open several avenues for future work. The first is to characterize the time-space trade-off between log log n and polylogn states. This question will likely require the development of analytic techniques parametrized by the number of states. A second direction is exploring the space-time trade-offs for approximately correct algorithms.
Proof. Recall that by definition, from a fully dense initial configuration every state in Λ n is producible. We begin by defining, for integers k ≥ 0, the function f (k) = n51 −2 k +1 . Alternatively, we have that f (k) 2 = f (k + 1)n/51. Let c = 1/2. Given the above, we notice that, with this choice it holds that, for sufficiently large n ≥ 2, • 3(c log log n) 2 /n ≤ (1/n) 0.99 , and • for 0 ≤ k ≤ c log log n, we have that f (k) ≥ max(n 0.99 , 50 √ n log n). We divide the execution into phases of index k ≥ 0, each containing n/2 consecutive interactions. For each 0 ≤ k ≤ |Λ n | − 1, we denote by C k the system configuration at the beginning of phase k. Inductive Claim.: We use probabilistic induction to prove the following claim: assuming that configuration C k is f (k)-rich with respect to the set of states S k , with probability 1 − 3|Λ n |/n, the configuration C k+1 is f (k + 1)-rich with respect to S k+1 .
For general k ≥ 0, let us fix the interactions up to the beginning of phase k, and assume that configuration C k is f (k)-rich with respect to the set of states S k . Further, consider a state q ∈ S k+1 . We will aim to prove that, with probability 1 − O(1/n), the configuration C k+1 satisfies contains state q with count ≥ f (k).
First, we define the following auxiliary notation. For any node r and set of nodes I, and define this counts the number of interactions between r and nodes in the set I, i.e. intcount(I, r) = |{ interaction j in phase k : there exists i ∈ I such that e j = (i, r) }|. Next, we define the set of nodes in a state s at the beginning of phase k as W (s) = {v : v ∈ V and C k (v) = s}. Finally, we isolate the set of nodes in state s at the beginning of phase k which did not interact during phase k as W (s) = {v : v ∈ W (s) and intcount(V, v) = 0}. Returning to the proof, there are two possibilities for the state q. The first is when q ∈ S k , that is, the state is already present at the beginning of phase k. But then, by assumption, state q has count ≥ f (k) at the beginning of phase k. To lower bound its count at the end of phase k, it is sufficient to examine the size of the set W (q). For a node v ∈ W (q), the probability that v ∈ W (q) is by Bernoulli's inequality. Therefore the expected size of W (q) is at least |W (q)|/2. Changing any interaction during phase k may change |W (q)| by at most 1, and therefore we can apply the method of bounded differences to obtain that Pr |W (q)| < |W (q)| 2 − n log n ≤ exp − n log n n = 1 n .
It remains to consider the case when q ∈ S k+1 − S k . Here, we know that there must exist states q i and q r in S k such that δ(q i , q r ) = q. We wish to lower bound the number of interactions between nodes in state q i and nodes in state q r throughout phase k. To this end, we isolate the set R of nodes which are in state q r at the beginning of phase k, and only interact once during the phase, i.e. R = {v : v ∈ W (q r ) and intcount(V, v) = 1}, and the set of nodes R , which are in R, and only interacted once during phase k, with a node in the set W (q i ), i.e. R = {v : v ∈ R and intcount(W (q i ), v) = 1}. Notice that any node in the set R is necessarily in state q at the end of phase k + 1. In the following, we lower bound the size of this set.
First, a simple probabilistic argument yields that E[|R|] ≥ |W (q r )|/4. Since each interaction in this phase affects the size of R by at most 2 (since it changes the count of both interaction partners), we can again apply the method of bounded differences to obtain that To lower bound the size of R , we apply again the method of bounded differences. We have that |W (q)| ≥ (2/5)f (k), and that |R| ≥ (1/20)f (k), we have that At the same time, we have that 1 50 which concludes the claim in this case as well. Finally, we can apply a union bound on the set of states to obtain that, with probability ≥ 1 − 3|Λ n |/n, Final Argument.: According to the lemma statement, we are considering an initial configuration in which all states which are present have count ≥ n/M , for some constant M ≥ 0. Let k 0 be the first positive integer such that n/M ≥ f (k 0 ). We have that the initial configuration is f (k 0 )-rich with respect to the set of initial states S 0 . By a variant of the previous inductive claim, we obtain that, for any integer 0 ≤ ≤ |Λ n | satisfying f (k 0 + ) ≥ max(n 0.99 , 10 √ n log n), at the beginning of phase , configuration C is f (k 0 + )-rich with respect to S .
Given a protocol P n , for a configuration c and a set of configurations Y , let us define T [c =⇒ Y ] as the expected parallel time it takes from c to reach some configuration in Y for the first time. Pr[c =⇒ Y ] stands for the probability of reaching a configuration in Y from c.
Claim A.2. In a system of n nodes, let γ > 0, f : N → R + , c : Λ n → N, and X, Y be sets of configurations, such that Pr[c =⇒ X] ≥ γ, and every transition sequence from every x ∈ X to some y ∈ Y has an f -bottleneck. Then T [c =⇒ Y ] ≥ γ n−1 2f (n)|Λn| 2 .
Proof. We will prove that for any x ∈ X, T [x =⇒ Y ] ≥ n−1 2f (n)|Λn| 2 holds, which implies the desired claim. By definition, every transition sequence from x to a configuration y ∈ Y contains an f -bottleneck, so it is sufficient to lower bound the expected time for the first f -bottleneck transition to occur from x before reaching Y . In any configuration c reachable from x, for any pair of states r 1 , r 2 ∈ Λ n such that r 1 , r 2 → p 1 , p 2 is a f -bottleneck transition in c, the definition implies that c(r 1 ) · c(r 2 ) ≤ f (n). Thus the probability that the next pair of agents selected to interact are in states r 1 and r 2 , is at most 2f (n) n(n−1) . Taking an union bound over all |Λ n | 2 possible such transitions, the probability that the next transition is f -bottleneck is at most |Λ n | 2 2f (n) n(n−1) . Bounding by a geometric variable with success probability 2f (n)|Λn| 2 n(n−1) , the expected number of interactions until the first f -bottleneck transition is at least n(n−1) 2f (n)|Λn| 2 . The expected parallel time is this quantity divided by n, completing the argument. Lemma A.3. Let P be a population protocol with |Λ n | ≤ 1/2 log log n states, and let D n ⊆ I n be a nonempty set of fully dense initial configurations. Fix a function f . Assume that for sufficiently large n, P stabilizes in expected time o n f (n)|Λn| 2 from all i n ∈ D n . Then, for all sufficiently large m ∈ N there is a configuration x m with m agents, reachable from some i ∈ D m and a transition sequence p m , such that: 1. x m (s) ≥ m 0.99 for all s ∈ Λ m , 2. x m =⇒ pm y m , where y m is a stable output configuration, and 3. p m has no f -bottleneck.
Proof. D n is a set of some legal initial configurations for n agents, which are all given to be fully dense. We know that the expected time to reach a stable output configuration from these initial configurations is finite. Hence if i =⇒ x m for i ∈ D m , then a stable output configuration y m must be reachable from x m through some transition sequence p m , but we also need x m and p m to satisfy the first and third requirements.
We know |Λ n | ≤ 1/2 log log n for all large enough n. Hence, by Lemma A.1, starting in any fully dense configuration i n ∈ D n , with probability at least 1 − (1/n) 0.99 , an n 0.99 -rich configuration is reachable. So n > 2, we get that Pr[i n =⇒ X n ] ≥ 1/2 where X n = {x | i n =⇒ x and (∀s ∈ Λ n )x(s) ≥ n 0.99 }.
Let Y n be a set of all stable output configurations with n agents. Suppose that every transition sequence from every configuration x ∈ X n to some y ∈ Y n has an f -bottleneck. Then, using Claim A.2, the expected time to stabilize from i ∈ D n is T [i n =⇒ Y n ] ≥ 1 2 · n−1 2f (n)|Λn| 2 = Θ( n f (n)|Λn| 2 ). But we know that the protocol stabilizes from i ∈ D n in time o( n f (n)|Λn| 2 ), implying that for all sufficiently large m, we can find x m ∈ X m from which it is possible to reach a stable output configuration in Y m without an f -bottleneck. First requirement is satisfied by the definition of X m , and we let p m be the transition sequence from x m to some y m ∈ Y m without an f -bottleneck.
Lemma A.4. Fix b ∈ N, and let B = |Λ n | 2 · b + |Λ n | · b. Given configurations x, y : Λ n → N in a system of n agents, such that for all states s ∈ Λ n we have x(s) ≥ B 2 and x =⇒ q y via a transition sequence q without a B 2 -bottleneck. Define ∆ = {d ∈ Λ n | y(d) ≤ b} to be the set of states whose count in configuration y is at most b. Then there is an order ∆ = {d 1 , d 2 , . . . , d k }, such that, for all j ∈ {1, . . . , k}, there is a transition α j of the form (d j , s j ) → (o j , o j ) with s j , o j , o j ∈ {d 1 , . . . , d j }, and α j occurs at least b times in q.
Proof. This part of the argument is identical to [CCDS14, DS15] and is described below for the sake of completeness.
Let k = |∆| and define ∆ k = ∆. We will construct the ordering in reverse, i.e. we will determine d j for j = k, k − 1, . . . , 1 in this order. At each step, we will define the next ∆ j−1 as ∆ j − {d j }.
We start by setting j = k. For all j we define Φ j : (Λ n → N) → N based on ∆ j as Φ j (c) = d∈∆ j c(d), i.e. the number of agents in states from ∆ j in configuration c. Notice that once ∆ j is well-defined, so is Φ j .
The following works for all j ≥ 1 and lets us construct the ordering. Because y(d) ≤ b for all states in ∆, it follows that Φ j (y) ≤ j · b ≤ |Λ n | · b. On the other hand, we know that x(d) ≥ b 2 for all d ∈ ∆ j , hence . Let c be the last configuration along q from x to y where Φ j (c ) ≥ b 2 , and r be the suffix of q after c . Then, r must contain a subsequence of transitions u each of which strictly decreases Φ j , with the total decrease over all of u being at least Let α : r 1 , r 2 → p 1 , p 2 be any transition in u. α is in u so it strictly decreases Φ j , and without loss of generality r 1 ∈ ∆ j . Transition α is not a (b 2 ) 2 -bottleneck, since u (and q) do not contain such bottlenecks, and all configurations c along u have c(d) < b 2 for all d ∈ ∆ j by definition of r. Hence, we must have c(r 2 ) > b 2 meaning r 2 ∈ ∆ j . Exactly one state in ∆ j decreases its count in transition α, but α strictly decreases Φ j , so it must be that both p 1 ∈ ∆ j and p 2 ∈ ∆ j . We take d j = r 1 , s j = r 2 , o j = p 1 and o j = p 2 .
There are |Λ n | 2 different types of transitions. As each transition in u decreases Φ j by exactly one and there are at least |Λ n | 2 · b such instances, at least one transition type must repeat in u at least b times, completing the proof.
Claim A.5. There exist configurations e : Λ m → N and z with z >0 ⊆ Γ g , such that e + u + x m =⇒ z . Moreover, we have an upper bound on the counts of states in e: ∀s ∈ Λ m : e(s) ≤ 2 |Λm| · g(m).
Proof. The proof is analogous to [DS15], but we consider a subsequence of the ordered transitions ∆ b = {d 1 , . . . , d k } obtained earlier by Lemma A.4. Since b(m) ≥ g(m), we can represent ∆ g = {d j 1 , . . . , d j l }, with j 1 ≤ . . . ≤ j l . We iteratively add groups of transitions at the end of transition sequence p m , (p m is the transition sequence from x m to y), such that, after the first iteration, the resulting configuration does not contain any agent in d j 1 . Next, we add group of transitions and the resulting configuration will not contain any agent agent in d j 1 or d j 2 , and we repeat this l times. In the end, no agents will be in states from ∆ g .
The transition ordering lemma provides us with the transitions to add. Initially, there are at most g(m) agents in state d j 1 in the system (because of the requirement in Theorem 3.1 on counts in u + y). So, in the first iteration, we add the same amount (at most g(m)) of transitions d j 1 , s j 1 → o j 1 , o j 1 , after which, as s j 1 , o j 1 , o j 1 ∈ {d 1 , . . . d j 1 }, the resulting configuration will not contain any agent in configuration d i 1 . If there are not enough agents in the system in state s j 1 already to add all these transitions, then we add the remaining agents in state in s j 1 to e. For the first iteration, we may need to add at most g(m) agents.
For the second iteration, we add transitions of type d j 2 , s j 2 → o j 2 , o j 2 to the resulting transition sequence. Therefore, the number of agents in d j 2 that we may need to consume is at most 3 · g(m), g(m) of them could have been there in y + u, and we may have added 2 · g(m) in the previous iteration, if for instance both o j 1 and o j 1 were d j 2 . In the end, we may need to add 3 · g(m) extra agents to e.
If we repeat these iterations for all remaining r = 3, . . . , l, in the end we will end up in a configuration z that contains all agents in states in Γ g as desired, because of the property of transition ordering lemma that s jr , o jr , o jr ∈ {d 1 , . . . , d jr }. For any r, the maximum total number of agents we may need to add to e at iteration r is (2 r − 1) · g(m). The worst case is when o j 1 and o j 1 are both d j 2 , and o j 2 , o j 2 are both d j 3 , etc.
Finally, it must hold that l < |Λ m |, because the final configuration contains m agents in states in Γ g and none in {d j 1 , . . . , d j l }, so Γ g cannot be empty. Therefore, the total number of agents added to e is g(m) · l r=1 (2 r − 1) < 2 l+1 · g(m) ≤ 2 |Λm| · g(m). This completes the proof because e(s) for any state s can be at most the number of agents in e, which is at most 2 |Λm| · g(m).
Proof. As in the proof of Claim A.5, we define a subsequence (j 1 ≤ j l ), ∆ g = {d j 1 , . . . , d j l } of ∆ b = {d 1 , . . . , d k } obtained using Lemma A.4. We start by the transition sequence p m from configuration x m to y, and perform iterations for r = 1, . . . k. At each iteration, we modify the transition sequence, possibly add some agents to configuration p, which we will define shortly, and consider the counts of all agents not in p in the resulting configuration. Configuration p acts as a buffer of agents in certain states that we can temporarily borrow. For example, if we need 5 agents in a certain state with count 0 to complete some iteration r, we will temporarily let the count to −5 (add 5 agents to p), and then we will fix the count of the state to its target value, which will also return the "borrowed" agents (so p will also appear in the resulting configuration). As in [DS15], this allows us let the counts of certain states temporarily drop below 0.
We will maintain the following invariants on the count of agents, excluding the agents in p, in the resulting configuration after iteration r: 1) The counts of all states (not in p) in ∆ g ∩ {d 1 , . . . , d r } match to the desired counts in e ∆g .
3) The counts in any state diverged by at most (3 r − 1) · 2 |Λm| · g(m) from the respective counts in y.
These invariants guarantee that we get all the desired properties after the last iteration. Let us consider the final configuration after iteration k. Due to the first invariant, the set of all agents (not in p) in states ∆ g is exactly e ∆g . All the remaining agents (also excluding agents in p) are in w, and thus, by definition, the counts of states in ∆ g in configuration w will be zero, as desired. The counts of agents in states ∆ b − ∆ g = {d 1 , . . . d k } − ∆ g that belong to w will be at least 2 |Λm| · g(m), due to the second invariant. Finally, the counts of agents in Γ b that belong to w will also be at least b(m) − 3 |Λm| · 2 |Λm| · g(m) ≥ 2 |Λm| · g(m), due to the third invariant and the fact that the states in Γ b had counts at least b(m) in y. Finally, the third invariant also implies the upper bound on counts in p. The configuration p will only contain the agents in states ∆ b , because the agents in Γ b have large enough starting counts in y borrowing is never necessary.
In iteration d r , we fix the count of state d r . Let us first consider the case when d r belongs to ∆ g . Then, the target count is the count of the state d r in e ∆g , which we are given is at most 2 |Λm| · g(m). Combined with the third invariant, the maximum amount of fixing required may be is 3 r−1 · 2 |Λm| · g(m). If we have to reduce the number of d r , then we add new transitions d r , s r → o r , o r , similar to Claim A.5 (as discussed above, not worrying about the count of s r possibly turning negative). However, in the current case, we may want to increase the count of d r . In this case, we remove instances of transition d r , s r → o r , o r from the transition sequence. The transition ordering lemma tells us that there are at least b(m) of these transitions to start with, so by the third invariant, we will always have enough transitions to remove. We matched the count of d r to the count in e ∆g , so the first invariant still holds. The second invariant holds as we assumed d r ∈ ∆ g and since by Lemma A.4, s r , o r , o r ∈ {d 1 , . . . , d r }. The third invariant also holds, because we performed at most 3 r−1 · 2 |Λm| · g(m) transition additions or removals, each affecting the count of any other given state by at most 2, and hence the total count differ by at most (3 r−1 − 1) · 2 |Λm| · g(m) + 2 · 3 r−1 · 2 |Λm| · g(m) = (3 r − 1) · 2 |Λm| · g(m). Now assume that d r belongs to ∆ b − ∆ g . If the count of d r is already larger than 2 |Λm| · g(m), than we do nothing and move to the next iteration, and all the invariants will hold. If the count is smaller than 2 |Λm| · g(m), then we set the target count to 2 |Λm| · g(m) and add or remove transitions like in the previous case, thus the first two invariants will again hold after the iteration. We are fixing the count from less than 2 |Λm| · g(m) to 2 |Λm| · g(m). Therefore, again considering the maximum effect on counts, the new difference can be at most (3 r−1 − 1) · 2 |Λm| · g(m) + 2 · 2 |Λm| · g(m), which is at most 3 r · 2 |Λm| · g(m). As in the previous case, we have enough transitions to remove and the third invariant also holds.
Lemma A.7. Consider a population protocol in a system with any fixed number of agents n, and an arbitrary fixed function h : N → N + such that h(n) ≥ 2 |Λn| . Let ξ(n) = 2 |Λn| . For all configurations c, c : Λ n → N, such that c >0 ⊆ Γ h (c) ⊆ Γ ξ (c ), any state producible from c is also producible from c . Formally, for any state s ∈ Λ n , c =⇒ y with y(s) > 0 implies c =⇒ y with y (s) > 0.
Proof. Since h(n) ≥ 2 |Λn| , for any state from Γ h (c), its count in c is at least 2 |Λn| . As Γ h (c) ⊆ Γ ξ (c ), the count of each of these states in c is also at least ξ(n) = 2 |Λn| . We say two agents have the same type if they are in the same state in c. We will prove by induction that any state that can be produced by some transition sequence from c, can also be produced by a transition sequence in which at most 2 |Λn| agents of the same type participate (ever interact). Configuration c only has agents with types (states) in Γ h (c), and configuration c also has at least 2 |Λn| agents for each of those types, the same transition sequence can be performed from c to produce the same state as from c, proving the desired statement.
The inductive statement is the following. There is a k ≤ |Λ n |, such that for each i = 0, 1, . . . , k we can find sets S 0 ⊂ S 1 ⊂ . . . ⊂ S k where S k contains all the states that are producible from c, and all sets S j satisfy the following property. Let A j be a set consisting of 2 j agents of each type in Γ h (c), out of all the agents in configuration c (we could also use c ), for the total of 2 j · |Γ h (c)| agents. There are enough agents of these types in c (and in c ) as j ≤ k ≤ |Λ n |. Then, for each 0 ≤ j ≤ k and each state s ∈ S j , there exists a transition sequence from c in which only the agents in A j ever interact and in the resulting configuration, one of these agents from A j ends up in state s.
We do induction on j and for the base case j = 0 we take S 0 = Γ h (c). The set A 0 as defined contains one (2 0 ) agent of each type in Γ h (c) = S 0 3 . All states in S 0 are immediately producible by agents in A 0 via an empty transition sequence (without any interactions).
Let us now assume inductive hypothesis for some j ≥ 0. If S j contains all the producible states from configuration c, then k = j and we are done. We will have k ≤ |Λ n |, because S 0 = ∅ and S 0 ⊂ S 1 ⊂ . . . S k imply that S k contains at least k different states, and there are |Λ n | total. Otherwise, there must be some state s ∈ S j that can be produced after an interaction between two agents both in states in S j , let us say by a transition α : r 1 , r 2 → s, p with r 1 , r 2 ∈ S j (or there is no state that cannot already be produced). Also, as S j contains at least j states out of |Λ n | total, and there is the state s ∈ S j , j < |Λ n | holds and the set A j+1 is well-defined. Let us partition A j+1 into two disjoint sets B 1 and B 2 where each contain 2 j agents from c for each type. Then, by induction hypothesis, there exists a transition sequence where only the agents in B 1 ever interact and in the end, one of the agents b 1 ∈ B 1 ends up in the state r 1 . Analogously, there is a transition sequence for agents in B 2 , after which an agent b 2 ∈ B 2 ends up in state r 2 . Combining these two transition and adding one instance of transition α in the end between agents b 1 and b 2 (in states r 1 and r 2 respectively) leads to a configuration where one of the agents from A j+1 is in state s. Also, all the transitions are between agents in A j+1 . Hence, setting S j+1 = S j ∪ {s} completes the inductive step.
Corollary A.8. Any monotonic population protocol with |Λ n | ≤ 1/2 log log n states for all sufficiently large number of agents n that stably computes correct majority decision for initial configurations with majority advantage n, must take Ω n 36 |Λn| ·|Λn| 6 ·max(2 |Λn| , n) 2 expected parallel time to convergence.
Proof. We set g(n) = max(2 |Λm|+1 , 4 n). For majority computation, initial configurations consist of agents in one of two states, with the majority state holding an n advantage in the counts. Therefore, the sum of two initial configurations of the same protocol is also a valid initial configuration, and thus monotonic populations protocols for majority computation must be input-additive. The bound is nontrivial only in a regime n ∈ o( √ n), which we will henceforth assume without loss of generality. The initial configurations we consider from I n will all have advantage n, and are all be fully dense.
Let us prove that for all sufficiently large m, in any final stable configuration y, strictly less than 2 |Λm| ≤ g(m)/2 agents will be in the initial minority state B m . The reason is that if c is the initial configuration of all m agents in state B m , the protocol must converge from c to a final configuration where the states correspond to decision Win B . By Lemma A.7, from any configuration that contains at least 2 |Λm| agents in B m it would also be possible to reach a configuration where some agent supports decision B m . Therefore, all stable final configuration y have at most g(m)/2 − 1 agents in initial minority state B m . This allows us to let u be a configuration of g(m)/2 + 1 ≥ 2 m + 1 agents in state B m .
Assume, to the contrary, that the protocol converges in parallel time o n 36 |Λn| ·|Λn| 6 ·max(2 |Λn| , n) 2 . We only consider initial configurations that are fully dense and contain (1+ )n 2 agents in state A n and (1− )n 2 agents in state B n , i.e. having majority state A n with advantage n. Let I n ⊆ I n contain only this fully dense initial configuration for each n and using Theorem 3.1 with I n instead of I n , we can find infinitely many configurations i and z of at most 3m agents, such that (1) i + u =⇒ z, (2) i ∈ I 2m , i.e. it is an initial configuration of 2m agents with majority state A 2m = A m and advantage 2 m. (3) |Λ m | = |Λ 2m | = |Λ 2m+|u| | = |Λ 3m | and by monotonicity, the same protocol is used for all number of agents between m and 3m, (4) z >0 ⊆ Γ g (y), i.e all agents in z are in states that have counts at least g(m) in some stable output configuration y of m agents.
To get the desired contradiction we will prove two things. First, z is actually a stable output configuration for decision Win A (majority opinion in i), and second, i + u is a valid initial configuration for the majority problem, but with majority state B m = B 2m+|u| . This will imply that the protocol converges to a wrong outcome, and complete the proof by contradiction.
If we could reach a configuration from z with any agent in a state s that maps to output Win B (γ m (s) = Win B ), then by Lemma A.7, from a configuration y (which contains 2 |Λm| agents in each of the states in Γ g (y)) we can also reach a configuration with an agent in a state s that maps to output Win B . However, configuration y is a final stable configuration for an initial configuration in I m with a majority A m .
Configuration i ∈ I 2m contains 2 m more agents in state A m states than in state B m . Configuration u consists of at least 2 m + 1 agents all in state B m . Hence, i + u which is a legal initial configuration from I 2m+|u| has a majority of agents in state B m .

B Analysis of the Majority Algorithm
The update rules in Figure 1 are chained, i.e. a cancel is followed by a join and a split. This is an optimization, applying as many possible reactions as possible. However, for the analysis we consider a slight modification, where we only apply split only if both join and cancel were unsuccessful.
For presentation purposes, we assume that n is a power of two, and when necessary, we assume that it is sufficiently large. Throughout this proof, we denote the set of nodes executing the protocol by V . We measure execution time in discrete steps (rounds), where each time step t corresponds to an interaction. The configuration at a given time t is a function c : V → Q, where c(v) is the state of the node v at time t. (We omit the explicit time t when clear from the context.) Recall that a value of a state x, y is defined as x − y and we will also refer to max(x, y) as the level of this node. We call x, y a mixed state if both x and y are non-zero, and a pure state otherwise. A mixed or pure node is a node in a mixed or a pure state, respectively.
The rest of this section is focused on proving the following result.
Theorem B.1. The Split-Join algorithm will never converge to the minority decision, and is guaranteed to converge to the majority decision within O(log 3 n) parallel time, w.h.p.
Correctness: We first prove that nodes never converge to the sign of the initial minority (safety), and that they eventually converge to the sign of the initial majority (termination). The first statement follows since given the interaction rules of the algorithm, the sum of the encoded values stays constant as the algorithm progresses. The proof follows by the structure of the algorithm.
Invariant B.2. The sum v∈V value(c(v)) never changes, for all reachable configurations c of the protocol.
This invariant implies that the algorithm may never converge to a wrong decision value. For instance, if the initial sum is positive, then positive values must always exist in the system. Therefore we only need to show that the algorithm converges to a state where all nodes have the same sign, which we do via a rough convergence bound, assuming an arbitrary starting configuration.
Lemma B.6. Let c be an arbitrary starting configuration. We define the (initial) sum of values as S := v∈V value(c(v)). By assumption, S = 0. With probability 1, the algorithm will reach a configurationĉ such that i) sgn(ĉ(v)) = sgn(S) for all nodes v ∈ V , and, ii) no node changes its sign in configurations c e reachable fromĉ, i.e. ∀c e reachable from c and v ∈ V : sgn(c e (v)) = sgn(ĉ(v)). For sufficiently large n, the convergence time toĉ is at most n 5 expected communication rounds, i.e. parallel time n 4 .
Convergence Time: Next, we bound the time until all nodes converge to the correct sign. Claim B.3. Consider a configuration where nδ out of the n nodes are in a mixed state, for δ ≥ 2(log n−1) n . In the next interaction round, the number of mixed nodes strictly decreases with probability at least δ 2 2(log n−1) .
Proof. Consider log n − 1 buckets corresponding to values 1, 2, 4, . . . , n/4. Let us assign mixed nodes to these buckets according to their states, where node in state x, y goes into bucket min(x, y). All nodes fall into one of the log n − 1 buckets because of the definition of (mixed) states.
If two nodes in the same bucket interact, either cancel or join will be successful, and since we consider the algorithm where split is not applied in this case, and the number of mixed nodes will strictly decrease. Thus, if there are d 1 , d 2 , . . . , d log n−1 nodes in the buckets, the number of possible interactions that decrease the number of mixed nodes is at least log . By the Cauchy-Schwartz inequality, d 2 i ≥ n 2 δ 2 log n−1 . Combining this with the above and using nδ ≥ 2(log n − 1) we get that the there are at least n 2 δ 2 4(log n−1) pairs of nodes whose interactions decrease the number of mixed nodes. The total number of pairs is n(n − 1)/2, proving the desired probability bound.
Claim B.4. Suppose f is a function such that f (n) ∈ O(poly(n)). For all sufficiently large n, the probability of having less than n 2 11 log n pure nodes in the system at any time during the first f (n) communication rounds is at most 1 − 1/n 5 .
Proof. Assume that this number became less than n 2 11 log n for the first time at time T after some number of communication rounds. Let t be the last time when the number of pure nodes was at least n 2 9 log n (such a time exists since the initial number of pure nodes is n) and let α be the number of communication rounds between t and T . The number of mixed nodes increases by at most two in each round, so α ≥ n 2 11 log n . By definition of t and T , at all times during the α communication rounds between t and T , at least n(2 9 log n−1) 2 9 log n ≥ n 2 nodes are mixed. Thus, by Claim B.3 in each of these communication rounds, the number of mixed nodes decreases by at least one with probability at least 1 8 log n . Let us describe by a random variable X ∼ Bin(α, 1 8 log n ) at least how often the number of mixed nodes decreased. Each node is pure or mixed, and by Chernoff Bound, the probability that the number of pure nodes increased less than α 16 log n times is Pr X ≤ α 16 log n = Pr X ≤ α 8 log n (1 − 1/2) ≤ exp − α 8 log n·2 2 ·2 ≤ exp − n 2 17 log 2 n On the other hand, in each of these α rounds, the number of pure nodes can decrease only if one of the interacting nodes was in a pure state. By definition of t and T , the number of such pairs is at most n 2 2 18 log 2 n + 2 n 2 (2 9 log n−1) 2 18 log 2 n ≤ 2n 2 2 9 log n . This implies that in each round the probability that the number of pure nodes will decrease is at most 1 2 6 log n . Let us describe the (upper bound on the) number of such rounds by a random variable Y ∼ Bin(α, 1 2 6 log n ). Since in each such round the number of pure nodes can decrease by at most 2, using Chernoff bound the probability that the number of pure nodes decreases by more than α 16 log n during the α communication rounds is at most Pr [Y ≥ α/(32 log n)] ≤ exp − n 2 19 log 2 n In order for the number of pure nodes to have decreased from n 2 9 log n at time t to n 2 11 log n at time T , either the number of mixed nodes must have increased by at most α 16 log n , or the number of pure nodes must have decreased by at least α 16 log n during the α communication rounds between t and T . Otherwise, the increase in mixed nodes would be more than the decrease in pure nodes. However, by union bound, the probability of this is at most exp − n 2 17 log 2 n + exp − n 2 19 log 2 n . We can now take union bound over the number of communication rounds until the number of pure nodes drops below n 2 11 log n (time T ). For at most f (n) ∈ O(poly(n)) rounds, we get that the probability of the number of pure nodes ever being less than n 2 11 log n is at most 1/n 5 for all large enough n.
Consider the high probability case of the above claim, where a fraction of pure nodes are present in every configuration in the execution prefix. We call a round a negative-round if, in the configuration c at the beginning of the round, there are at least n 2 11 log n pure nodes and at least half of the pure nodes encode a non-positive value. Analogously, we call a round a positive-round if there are at least n 2 11 log n pure nodes, at least half of which encode a non-negative value. A round can be simultaneously negative and positive, for instance when all pure nodes encode value 0. Next claim establishes the speed at which the maximum level in the system decreases. The proof, given in full in the Appendix, follows by bounding the probability that a node with the maximum level meets a pure node with value 0 or a value of the opposite sign. This results in a split (or cancel) reaction decreasing the level of the node, and we use Chernoff and Union Bounds to bound the probability that the node avoids such a meeting for significant time.
We get a condition for halving the maximum level (among positive or negative values) in the system with high probability. The initial levels in the system is n, which can only be halved log n times for each sign. Combining everything results in the following claim: Claim B.8. There exists a constant β, such that if during the first 2βn log 3 n rounds the number of pure nodes is always at least n 2 11 log n , then with probability at least 1 − 2 log n n 5 , one of the following three events occurs at some point during these rounds: 1. Nodes only encode values in {−1, 0, 1}; 2. There are less than n 2 12 log n nodes with non-positive values, all encoding 0 or −1, 3. There are less than n 2 12 log n nodes with non-negative values, all encoding 0 or 1. Final Argument: To see how this claim can be used to obtain the convergence upper bound, let us assume without loss of generality that the initial majority of nodes was in A (positive) state, i.e. a > b.
Setting β as in Claim B.8, by Claim B.4, with high probability, we have at least n 2 11 log n pure nodes during the first 2βn log 3 n rounds. Thus, w.h.p. during these rounds the execution reaches a configuration where one of the three events from Claim B.8 holds. Consider this point T in the execution.
By our assumption about the initial majority and Invariant B.2, v∈V value(c(v)) = n 2 holds in every reachable configuration c. The third event is impossible, because the total sum would be negative. In the first event, the total sum is n 2 ≥ n of n encoded values each being −1, 0 or 1. Therefore, in this case, all nodes must be in state 1, 0 and we are done.
In the second event implies there are at least n(2 12 log n−1) 2 12 log n ≥ 2n 3 nodes encoding strictly positive values. Hence, at time T during the first 2βn log 3 n rounds there are at least n/3 more strictly positive than strictly negative values. Moreover, −1's are the only strictly negative values of the nodes at point T , and this will be the case for the rest of the execution because of the update rules. After time T , we have Claim B.9. Consider a configuration where all nodes with strictly negative values encode −1, while at least  In the remaining low probability event, with probability at most log n+1 n 5 , the remaining number of rounds is at most O(n 5 ) by Lemma B.6. Therefore, the same O(n log 3 n) bound also holds in expectation, Claim B.5. There are at most 2n 2 split reactions in any execution.
Proof. A level of a node in state s = x, y is defined as level (s) = max(x, y). Consider a node in a state with level l. Then, we say that the potential of the node is φ(l) = 2l for l > 0 and φ(0) = 1. In any configuration c, the potential of the system is Φ(c) = n i=1 φ(level (s i )). Then, the potential of the system in the initial configuration is (2n) = 2n 2 , and it can never fall below (1) = n. By the interaction rules of the algorithm, potential of the system never increases after an interaction, and it decreases by at least one after each successful split interaction. This implies the claim.
Lemma B.6. Let c be an arbitrary starting configuration. Define S := v∈V value(c(v)) = 0. With probability 1, the algorithm will reach a configurationĉ such that sgn(ĉ(v)) = sgn(S) for all nodes v ∈ V . Moreover, in all later configurations c e reachable fromĉ, no node can ever have a different sign, i.e. ∀v ∈ V : sgn(c e (v)) = sgn(ĉ(v)). For sufficiently large n, the convergence time toĉ is at most n 5 expected communication rounds, i.e. parallel time n 4 .
Proof. Assume without loss of generality that the sum S is positive.
We estimate the expected convergence time by splitting the execution into three phases. The first phase starts at the beginning of the execution, and lasts until either i) no node encodes a strictly negative value or ii) each node encodes a value in {−1, 0, 1}, i.e. all nodes are in states 1, 0 , 0, 0 + . 0, 0 − or 0, 1 .
Due to Invariant B.2, at least one node encodes a strictly positive value. Also, by definition, during the first phase there is always a node encoding a strictly negative value. Moreover, there is a node in state x, y with max(x, y) > 1. Assume that x > y for this node. Then, if there is another node in state 0, y 2 for any y 2 , then with probability at least 1/n 2 these two nodes interact in the next round resulting in a split reaction. Otherwise, every node x 1 , y 1 that encodes a strictly negative value must have min(x 1 , y 1 ) > 0. At least one such node exists and if there is another node in state x 2 , 0 for any x 2 , then again with probability at least 1/n 2 a split reaction occurs in the next round. The case of x < y is analogous and we get that during the first phase, if there is no pair whose interaction would result in a split reaction, all nodes must be in states x, y with min(x, y) > 0, i.e. in mixed states. By Claim B.3, with probability at least 1 2(log n−1) a pure node appears after the next communication round and by the above argument, if the first phase has not been completed, in the subsequent round a split reaction will occur with probability at least 1/n 2 . Therefore, during the first phase, the expected number of rounds until the next split reaction is at most 4n 2 (log n − 1). By Claim B.5, there can be at most 2n 2 split reactions in any execution, thus the expected number of communication rounds in the first phase is at most 8n 4 (log n − 1).
The second phase starts immediately after the first, and ends when no node encodes a strictly negative value. Note that if this was already true when the first phase ended, then the second phase is trivially empty. Consider the other case when all nodes encode values −1, 0 and 1 at the beginning of the second phase. Under these circumstances, because of the update rules, no node will ever be in a state x, y with max(x, y) > 1 in any future configuration. Also, the number of nodes encoding non-zero values can only decrease. In each round, with probability at least 1/n 2 , two nodes with values 1 and −1 interact, becoming 0, 0 + and 0, 0 − . Since this can only happen n/2 times, the expected number of communication rounds in the second phase is at most n 3 /2.
The third phase lasts until the system converges, that is, until all nodes with value 0 are in state 0, 0 + . By Invariant B.2, S > 0 holds throughout the execution, so there is at least one node with a positive sign and non-zero value. There are also at most n − 1 conflicting nodes with negative sign, all in state 0, 0 − . Thus, independently in each round, with probability at least 1/n 2 , a conflicting node meets a node with strictly positive value and becomes 0, 0 + , decreasing the number of conflicting nodes by one. The number of conflicting nodes can never increase and when it becomes zero, the system has converged to the desired configurationĉ. Therefore, the expected number of rounds in the third phase is at most n 3 .
Combining the results and using the linearity of expectation, the total expected number of communication rounds before reachingĉ is at most n 3 (8n(log n − 1) + 1/2 + 1) ≤ n 5 for sufficiently large n. Finite expectation implies that the algorithm converges with probability 1. Finally, when two nodes with positive sign meet, they both remain positive, so any configuration c e reachable fromĉ has the correct signs.
Claim B.7. Let w > 1 be the maximum level among the nodes with a negative (resp., positive) sign. There is a constant β, such that after βn log 2 n positive-rounds (resp., negative-rounds) the maximum level among the nodes with a negative (resp., positive) sign will be at most w/2 with probability at least 1 − 1 n 5 . Proof. We will prove the claim for nodes with negative values. (The converse claim follows analogously.) Fix a round r, and recall that w > 1 is the maximum level of a node with a negative value at the beginning of the round. Let U be the set of all nodes with negative values and the same level w at the beginning of the round, and let u = |U |. We call these nodes target nodes.
By the structure of the algorithm, the number of target nodes never increases and decreases by one in every eliminating round where a target node meets a pure node with a non-negative value, due to a split or cancel reaction. Consider a set of αn log n consecutive positive-rounds after r, for some constant α > 2 12 . In each round, if there are still at least u/2 target nodes, then the probability of this round being eliminating is at least u/2 2 12 n log n (since in a positive round at least half of n 2 11 log n pure nodes have non-negative value). Let us describe the process by considering a random variable Z ∼ Bin(αn log n, u/2 2 12 n log n ), where each success event corresponds to an eliminating round. By a Chernoff Bound, the probability of having αn log n iterations with at most u/2 eliminations is at most: 2 13 α 2 For sufficiently large α and u ≥ log n, the probability of this event is at most 1 n 6 for αn log n positiverounds. Applying the same rationale iteratively as long as u ≥ log n, we obtain by using a Union Bound that the number of target nodes will become less than log n within αn log n(log n − log log n) positive-rounds, with probability at least 1 − log n−log log n n 6 . Finally, we wish to upper bound the remaining number of positive-rounds until no target node remains. Again for sufficiently large α, but when u < log n, we get from the same argument as above that the number of target nodes is reduced to u/2 within αn log 2 n u consecutive positive-rounds with probability 1/n 6 . So we consider increasing numbers of consecutive positive-rounds, and obtain that no target nodes will be left after at most αn log n + 2αn log n + . . . + αn log 2 n ≤ 2αn log 2 n positive-rounds, with probability at least 1− log log n n 6 , where we have taken the union bound over log log n events. The original claim follows by setting β = 3α, taking Union Bound over the above two events (u ≥ log n and u < log n) and log n ≤ n.
Claim B.8. There exists a constant β, such that if during the first 2βn log 3 n rounds the number of pure nodes is always at least n 2 11 log n , then with probability at least 1 − 2 log n n 5 , one of the following three events occurs at some point during these rounds: 1. Nodes only encode values in {−1, 0, 1}; 2. There are less than n 2 12 log n nodes with non-positive values, all encoding 0 or −1, 3. There are less than n 2 12 log n nodes with non-negative values, all encoding 0 or 1.
Proof. We take a constant β that works for Claim B.7. Since there are at least n 2 11 log n pure node at all times during the first 2βn log 3 n rounds, each round during this interval is a negative-round, a positive-round, or both. We call maximum positive (resp. negative) level the maximum level among all the nodes encoding nonnegative (resp. non-positive) values. Unless the maximum positive level in the system is ≤ 1, by Claim B.7, a stretch of βn log 2 n negative-rounds halves the maximum positive level, with probability at least 1 − 1 n 5 . The same holds for stretches of βn log 2 n positive-rounds and the maximum negative level.
Assume that none of the three events hold at any time during the first 2βn log 3 n rounds. In that case, each round can be classified as either: • a negative-round where the maximum positive level is strictly larger than 1, or • a positive-round where the maximum negative level is strictly larger than 1. To show this, without a loss of generality consider any positive-round (we showed earlier that each round is positive-round or a negative-round). If the maximum negative level is > 1 then the round can be classified as claimed, thus all non-positive values in the system must be 0 or −1. Now if there are less than n 2 12 log n such nodes, then we have the second event, so there must be more than n 2 12 log n nodes encoding 0 and −1. However, all these nodes are pure, so the round is simultaneously a negative-round. Now if the maximum positive level is > 1 then the round can again be classified as claimed, and if the maximum positive level is at most 1, then all nodes in the system are encoding values −1, 0 or 1 and we have the first event.
Thus, each round contributes to at least one of the stretches of βn log 2 n rounds that halve the maximum (positive or negative) level, w.h.p. However, this may happen at most 2 log n times. By applying Claim B.7 2 log n times and the Union Bound we get that after the first 2βn log 3 n rounds, with probability at least 1 − 2 log n n 5 only values −1, 0 and 1 may remain. However, this is the same as the first event above. Hence, the probability that none of these events happen is at most 2 log n n 5 . Claim B.9. Consider a configuration where all nodes with strictly negative values encode −1, while at least 2n 3 nodes encode strictly positive values. The number of rounds until convergence is O(n log n) in expectation and O(n log 2 n) with high probability.
Proof. In any configuration, let us call conflicting any node that encodes −1, and target node any node that has a strictly positive value. Because of the structure of the algorithm, and that in configuration c the only nodes with non-positive sign encode −1 or 0, in all configurations reachable from c nodes with negative values will also only encode −1 or −0. Moreover, the number of conflicting nodes can never increase after an interaction. Observe that the number of conflicting nodes decreases by one after an interaction where a target node (with a stritly positive value) meets a node with value −1, while the number of target nodes may also decrease by at most 1. This is because a split reaction happens on the positive component of the target node (since the positive component of the conflicting node is 0) and both nodes get value ≥ 0 after the interaction. There are at least n/3 more target nodes than conflicting nodes in c, therefore, in every later configuration, there must always be at least n/3 target nodes.
Let us estimate the number of rounds until each conflicting node has interacted with a target node, at which point no more conflicting nodes may exist. Let us say there were x conflicting nodes in configuration c. The expected number of rounds until the first conflicting node meets a target node is at most 3n x , since the probability of such an interaction happening in each round is at least x n · n 3n . The expected number of rounds for the second node is then 3n (x−1) , and so on. By linearity of expectation, the expected number of rounds until all conflicting nodes are eliminated is O(n log x) ≤ O(n log n).
At this point, all nodes that do not have a positive sign must be in state 0, 0 − . If we redefine conflicting to describe these nodes, it is still true that an interaction of a conflicting node with a target node brings the conflicting node to state 0, 0 + , decreasing the number of conflicting nodes. As we discussed at least n/3 target nodes are still permanently present in the system. By the structure of the algorithm no interaction can increase the number of conflicting nodes, and the system converges when all conflicting nodes are eliminated. This takes expected O(n log n) rounds by exactly the same argument as above.
To get the high probability claim, simply observe that when there are x conflicting nodes in the system, a conflicting node will interact with a target node within 3nO(log n) x rounds, with high probability. The same applies for the next conflicting node, etc. Taking Union Bound over these events gives the desired result.

C Synthetic Coins
Proof. If two agents both with coin values one are selected, the number of ones decreases by two. If both coin values are zero, it increases by two, and otherwise stays the same. Hence, we have that Thus, we get a recursive dependence E[X i+m ] = E[X i+m−1 ] · (1 − 4/n) + 2, that gives by telescoping.

D Analysis of the Leader Election Algorithm
Lemma D.1. All nodes can never be minions. A configuration with n − 1 minions must have a stable leader, meaning that the non-minion node will never become a minion, while minions will remain minions.
Proof. Assume for contradiction that all nodes are minions at some time T , and let u be a maximum (.payoff , .level ) pair (lexicographically) among all the minions at this time. No node in the system could ever have had a larger pair, because no interaction can decrease a pair. The minions only record the values of such pairs they encounter, and never increase them, so there must have been a contender in the system with a payoff and level pair u that turned minion by time T . Among all such contenders, consider the one that turned minion the last. It could not have interacted with a minion, because no minion (and no node) in the system ever held a larger pair. On the other hand, even if it interacted with another contender, the contender also could not have held a larger pair. Thus, it could only have been an interaction with another contender, that held the same pair and a larger coin value used as a tie-breaker. However, that interaction partner would remain a contender and and must have turned minion later, contradicting our assumption that the interaction we considered was the last one where a contender with a pair u got eliminated. By the structure of the algorithm, minions can never change their mode. In any configuration with n − 1 minions, the only non-minion must remain so forever, and thus be a stable leader, because otherwise we would get n minions and violate the above argument.
Lemma D.2. With probability 1−O(1)/n 3 , after O(n log n) interactions, all agents will be in the competition stage, that is, either in tournament or minion mode, with maximum payoff at least log n/2 and at most 9 log n, and at most 5 log n agents will have this maximum payoff .
Proof. Let us call the first 2n interactions the irrelevant interactions, and all interactions after that the relevant interactions. By Theorem 4.1, during relevant interactions, with probability at least 1 − 2 exp(−n/4), there are at least n(1/2−1/2 8 ) and at most n(1/2+1/2 8 ) agents holding each possible coin value. Taking an union bound, this holds for all of the first n 4 relevant interactions with probability at least 1 − 2n 4 exp(n/4) < 1 − 1/n 3 . From now on, we will consider this high probability event of synthetic coin working properly and implicitly take unoin bound over it.
During any relevant interaction, any agent in lottery mode with probability at least 1/2 − 1/2 8 observes 0 and changes its mode to the tournament. Hence, the probability that it increases its payoff more than 5 log n times is at most (1/2 + 1/2 8 ) 5 log n ≤ 1/n 4 . Taking the union bound over all agents gives that the increase in payoffs in the relevant interactions for all agents are less than 5 log n with probability at least 1 − 1/n 3 . During the first 2n irrelevant interactions, by the Chernoff bound, the probability that a given agent interacts more than 4 log n times is at most 1/n 4 . Taking an union bound, all agents interact at most 4 log n times with probability at least 1 − 1/n 3 . Even if they increase their payoff each time, in total, with probability at least 1 − O(1)/n 3 , all agents will have payoffs at most 9 log n.
Since every agent stays in seeding mode for four interactions, we can find at least n/2 agents, who move to lottery mode during a relevant interaction. Consider any one of the n/2 agents. By assumption, the agent will have probability at least 1/2 − 1/2 8 of finalizing its payoff and moving to tournament mode. The probability that the payoff of this agent will be larger than log n/2 is thus at least (1/2 − 1/2 8 ) log n/2 ≥ 1/n 0.6 . If the payoff is indeed larger, we are done, otherwise, we can find another agent among the n/2 − log n/2 whose interactions we have not yet considered, and analogously get that with probability at least 1/n 0.6 , it would get a payoff at least log n/2. We can continue this process, and will end up with about n/ log n agents, whose interactions were completely independent, and because of the bias, each of them had a probability of at least 1/n 0.6 of getting a larger payoff than log n/2. If we describe this process as a random variable Bin n log n , 1 n 0.6 with expectation n 0.4 / log n, we get by the Chernoff Bound that the probability of no node getting ≥ log n/2 payoff is extremely low (in particular, less than 1/n 3 ).
Again, considering all the high probability events from above, we know that the maximum payoff in the system is between log n/2 and 9 log n. Consider any fixed payoff k in this interval, and let us say it is the maximum. Then, any agent that reaches this payoff, has to flip 0, but they might flip 1 with probability at least 1/2 − 1/2 8 . Thus, the probability that at least 12 log n agents will stop exactly at payoff k is at most (1/2 + 1/2 8 ) 5 log n ≤ 1/n 4 . Taking the union bound over at most 9 log n < n payoffs, and the above high probability events, we get that with probability at most 1 − O(1)/n 3 , at most 5 log n agents will have the maximum payoff, which will be between log n/2 and 9 log n.
It only remains to prove that after O(n log n) interactions, all agents will be in the tournament stage with probability 1 − O(1)/n 3 , which is a standard high probability coupon collector argument. Recall that after 2n irrelevant interactions, with probability at least 1 − 1/n 3 synthetic coins work properly for the next n 4 interactions, and thus, each agent that has not yet moved to the tournament stage and interacts, has probability of at least 1/2 − 1/2 8 of doing so. Thus, after O(n log n) interactions, by the Chernoff bound, a given agent will interact O(log n) times with very high probability and move to the tournament stage at least during one of these O(log n) interactions also with very high probability. Taking union bound over all agents and these events completes the proof.
Lemma D.3. with probability at least 1 − O(1)/n 3 , only one contender reaches level = 3 log n/ log log n, and it takes at most O(n log 5.3 log log n) interactions for a new level to be reached up to .
Proof. By our assumption on m, it holds that m log m ≥ 3 log n log log n , so this level can always be reached. We consider the high probability case in Lemma D.2, which occurs with probability ≥ 1 − O(1)/n 3 . Hence, we need to prove that the probability that more than one competitor reaches level is also at most O(1)/n 3 .
Consider some competitor v which just increased the maximum level among competitors in the system. Until some other competitor reaches the same level, v will turn every interaction partner into its minion. Furthermore, as in epidemic spreading, these minions will also turn their interaction partners into minions of the highest level contender v. Let the payoff and level pair of this competitor be u. We call a node whose pair also at least u an up-to-date node; the node is out-of-date otherwise. Initially, only the contender v that reached the maximum level is up-to-date.
We will show that if in some configuration x < n nodes are up-to-date, after a phase of 16n(n−1) log n 4x(n−x) interactions, at least x + 1 nodes will be up-to-date with probability at least 1 − 1 n 5 . Up-to-date nodes may never become out-of-date. On the other hand, an out-of-date node becomes up-to-date itself after an interaction with any up-to-date node. If we have x up-to-date nodes, in each interaction, the probability that an out-of-date node interacts with an up-to-date node increasing the number of up-to-date nodes to x + 1, is 2x(n−x) n(n−1) , which we denote by 1/α. To probability that this never happens during 16n(n−1) log n 4x(n−x) = 8α log n interactions is then (1 − 1/α) 8α log n ≤ 1 − 1/n 5 . An Union Bound over at most n phases gives that with probability at least 1 − 1/n 4 , after at most n−1 x=1 16n(n − 1) log n 4x(n − x) ≤ 16(n − 1) log n 4 n−1 x=1 1 x + 1 n − x ≤ 16n log 2 n rounds, all nodes will have value at least u. Taking an union bound over all possible levels < log n < n, and all previous events, we get that with probability at least 1 − O(1)/n 3 , once a contender reaches some level, unless some other contender reaches the same level within the next 16n log 2 n interactions, the original node will turn every other node into minions and become a stable leader. Once some contender has increased the maximum level, it needs to observe between 4.2 log log n and 4.2(log log n + log 9 + 1) consecutive ones to increase a level, as with high probability we knew that the payoff was between log n/2 and 9 log n and we set the phase size to 4.2(log payoff +1). Notice that all nodes that did not get a maximum payoff are not considered as contenders, because they will all be eliminated by maximum payoff contenders within O(n log n) interactions.
A given node at each iteration observes coin value one with probability at least (1/2 − 1/2 8 ), so the probability that a stretch of 4.2 log log n + O(1) consecutive interactions results in a level increase is at least Θ(1/ log 4.3 n). If we consider an interval containing O(n log 5.3 n log log n) interactions, then the agent increases the level in expectation O(log 5.3 n/ log 4.3 n) = O(log n) times and by the Chernoff bound, at least once with high probability.
For the rest of the argument, we will bound the probability that any of the other contenders, whose number is at most 5 log n by Lemma D.2, will be able to increment their level during an arbitrary stretch of 6 log log n + 12 consecutive interactions. This probability will be low, and therefore it is likely that the process will terminate after a level increase.
More precisely, once a new level is reached after a level increment, the nodes have 16n log 2 n interactions to increment to the same level, or they will soon all become minions. To do so, they should all have at least one iteration of observing at least 4.2 log log n consecutive ones.
Hence, there can be at most 5 log n · Θ(log 2 n/ log log n) such interaction intervals and each interaction interval has probability at most (1/2 + 1/2 8 ) 4.2 log log n ≤ 1/ log 4 n of success. Hence, by taking sufficiently large n, we can make the expectation of the number of successful iterations be less than 1/ log n.
Hence, the probability that there is no second survivor among contenders at each level (which would correspond to a stable leader being elected) is at most 1/ log n, every time the maximum level is incremented. The probability that this does not happen for all = 3 log n log log n levels is then at most ( 1 log n ) ≤ 1 n 3 .
Lemma D.4. The expected parallel time until convergence is O(log 5.3 n log log n).
Proof. To get the same bound on expected parallel time as in the with high probability case, we should incorporate the expected time in the low probability event. The lottery stage takes expected O(n log n) interactions by standard coupon collector argument (see the argument in Lemma D.2). During competition, as we saw in Lemma D.3, with high probability, a new level is reached within every O(n log 5.3 n log log n) interactions, and with more than constant probability a single contender remains after each level. Therefore, in the high probability case, only constantly many levels will be used in expectation and expected parallel time will be O(log 5.3 n log log n).
Otherwise, during competition, recall that non-minions can always eliminate each other in direct interactions comparing their payoffs, levels, and the coin as a tie-breaker. So, for any given two non-minion nodes x and y, in every interaction, there is a probability of at least O(1/n 2 ) that they meet, and one eliminates each other for certain if they had different coin values. If not, then with probability at least 1/n, one of the nodes, say x, interacts with some other node in this interaction, and then immediately afterward, interacts with y, this time with different coin values. Hence, in every two iterations, with probability at least O(1/n 3 ), the number of contenders decreases by at least one. The expected number of interactions until one remains is O(n 4 ), thus parallel time O(n 3 ) with probability at most O(1/n 3 ), which gives negligible expectation O(1) on parallel time in this low probability case.