We study population protocols, a model of distributed computing appropriate for modeling well-mixed chemical reaction networks and other physical systems where agents exchange information in pairwise interactions, but have no control over their schedule of interaction partners. The majority problem is that of determining in an initial population of$n$agents, each with one of two opinions$A$or B, whether there are more A, more B, or a tie. A stable protocol solves this problem with probability 1 by eventually entering a configuration in which all agents agree on a correct consensus decision of A, B, or T, from which the consensus cannot change. We describe a protocol solving this problem using O(log n) states (log log$n$+ O(1) bits of memory) and optimal expected time$O$(log$n$). The number of states$O$(log$n$) is known to be optimal for polylogarithmic time stable protocols that are “output dominant” and “monotone” [1]. These are two natural constraints satisfied by our protocol, making it simultaneously time- and state-optimal for that class. We introduce a key technique called a “fixed resolution clock” to achieve partial synchronization. Our protocol is nonuniform: the transition function has the value [log$n$] encoded in it. We show that the protocol can be modified to be uniform, while increasing the state complexity to Θ (log$n$log log n).

We study population protocols, a model of distributed computing where agents exchange information in pairwise interactions, but have no control over their schedule of interaction partners. The well-studied majority problem is that of determining in an initial population of n agents, each with one of two opinions A or B, whether there are more A, more B, or a tie. A stable protocol solves this problem with probability 1 by eventually entering a configuration in which all agents agree on a correct consensus decision of A, B, or T, from which the consensus cannot change. We describe a protocol that solves this problem using O(log n) states (log log n + O(1) bits of memory) and optimal expected time O(log n). The number of states O(log n) is known to be optimal for the class of polylogarithmic time stable protocols that are "output dominant'' and "monotone''. These are two natural constraints satisfied by our protocol, making it simultaneously time- and state-optimal for that class. Our protocol is nonuniform : the transition function has the value log n encoded in it. We show that the protocol can be modified to be uniform, while increasing the state complexity to Θ(log n log log n).

The standard population protocol model assumes that when two agents interact, each observes the entire state of the other. We initiate the study of message complexity for population protocols, where an agent’s state is divided into an externally-visible message and externally-hidden local state. We consider the case of O(1) message complexity. When time is unrestricted, we obtain an exact characterization of the stably computable predicates based on the number of internal states s(n): If s(n) = o(n) then the protocol computes semilinear predicates (unlike the original model, which can compute non-semilinear predicates with s(n) = O(log n)), and otherwise it computes a predicate decidable by a nondeterministic O(n log s(n))-space-bounded Turing machine. We then introduce novel O(polylog(n)) expected time protocols for junta/leader election and general purpose broadcast correct with high probability, and approximate and exact population size counting correct with probability 1. Finally, we show that the main constraint on the power of bounded-message-size protocols is the size of the internal states: with unbounded internal states, any computable function can be computed with probability 1 in the limit by a protocol that uses only 1-bit messages.

We study uniform population protocols: networks of anonymous agents whose pairwise interactions are chosen at random, where each agent uses an identical transition algorithm that does not depend on the population size n. Many existing polylog(n) time protocols for leader election and majority computation are nonuniform: to operate correctly, they require all agents to be initialized with an approximate estimate of n (specifically, the value łfloorłog n\rfloor). Our first main result is a uniform protocol for calculating łog(n) \pm O(1) with high probability in O(łog^2 n) time and O(łog^4 n) states (O(łog łog n) bits of memory). The protocol is not terminating : it does not signal when the estimate is close to the true value of łog n. If it could be made terminating with high probability, this would allow composition with protocols requiring a size estimate initially. We do show how our main protocol can be indirectly composed with others in a simple and elegant way, based on leaderless phase clocks, demonstrating that those protocols can in fact be made uniform. However, our second main result implies that the protocol cannot be made terminating, a consequence of a much stronger result: a uniform protocol for any task requiring more than constant time cannot be terminating even with probability bounded above 0, if infinitely many initial configurations are dense : any state present initially occupies Ømega(n) agents. (In particular no leader is allowed.) Crucially, the result holds no matter the memory or time permitted.

We study population protocols: networks of anonymous agents whose pairwise interactions are chosen uniformly at random. The size counting problem is that of calculating the exact number n of agents in the population, assuming no leader (each agent starts in the same state). We give the first protocol that solves this problem in sublinear time. The protocol converges in O(log n log log n) time and uses O(n^60) states (O(1) + 60 log n bits of memory per agent) with probability 1-O((log log n)/n). The time to converge is also O(log n log log n) in expectation. Crucially, unlike most published protocols with omega(1) states, our protocol is uniform: it uses the same transition algorithm for any population size, so does not need an estimate of the population size to be embedded into the algorithm.