UC Davis

The population protocols model describes a population of n finite-state computational agents, whose states change through successive pairwise interactions. Crucially, the agents have no control over the interaction schedule, and agents in the same state are indistinguishable. One motivating example are chemical reaction networks, viewing the agents as molecules undergoing pairwise collisions and changing state via reactions. Since this model is mathematically fundamental, equivalent processes have been independently studied in many fields.This work contributes new software tools for simulating population protocols, studies the time and space complexity of fundamental tasks, and explores various additional constraints on the model that ensure reliability, low bandwidth, and composability.

A standard choice of dynamics is to pick a uniform random pair of agents to interact at each step. The set of states and update rule then give a discrete Markov process. In the first part of this work, we introduce ppsim, a software package for simulating such processes. Complex protocols can be succinctly described in Python code, and are simulated by an algorithm which is asymptotically faster than the standard algorithm which repeatedly samples interacting pairs of agents and updates their state.

Chemical reaction networks (CRNs) are typically described by continuous time dynamics, where the Gillespie algorithm is able to sample trajectories from the chemical master equation. A CRN with only unimolecular (1 input, 1 output) or bimolecular (2 input, 2 output) reactions, with arbitrary rate constants, can be faithfully represented by a continuous time population protocol. In this way, \ppsim is able to exactly sample the same chemical master equation, while achieving asymptotic gains in running time that can exactly simulate hundreds of billions of reactions in seconds.

What differentiates population protocols from other models that capture the same dynamics is that, coming from the field of distributed computing, it studies which computational tasks the population can perform. Typically, there is some global property of the initial configuration, and the task is to converge to a configuration where each agent locally has knowledge of this property. The correct output must be reached with probability 1 and then be stable, unable to be changed by future interactions. A prototypical example is the majority problem. There, the initial configuration has two states A and B, and the agents must determine whether there are more A, more B, or a tie.

A recent line of work has established progressively more efficient protocols for solving the majority problem.In the second part of this work, we describe and analyze a majority protocol using O(log n) states and taking expected time O(log n) (O(n log n) pairwise interactions). Existing lower bounds for protocols with natural constraints show that this protocol is asymptotically optimal in both state space and convergence time.

The other most studied problem in population protocols is leader election. There, the population must reach a configuration with a unique agent in a designated leader state. Typically, the entire population starts in some fixed initial state, but the additional self-stabilizing constraint requires the protocol to correctly converge starting from any possible initial configuration. In the third part of this work, we develop multiple new protocols for solving self-stabilizing leader election, exhibiting a trade-off in state space and convergence time.

In the original model, the agents' state set was fixed and independent of the population size n. Most recent results, including the work above, allow the number of states to scale with the population size. The standard transition ruleassumes that when two agents interact, each observes the entire state of the other agent. In the fourth part of this work, we initiate the study of message complexity for population protocols, where the state of an agent is divided into an externally-visible message and an internal component, and only the message can be observed by the other agent in an interaction. The focus is on constant-size message complexity, so only the number of internal states can grow with the population size. This models a regime where communication bandwidth between agents is more limited than internal storage. Without restricting convergence time, we obtain an exact characterization of the computational power, based on the number of internal states. We also introduce multiple novel O(polylog(n)) expected time protocols, solving problems of leader election, general purpose broadcast, and population size counting.

The final part of this work considers the more general model of discrete chemical reaction networks, which now allow reactions such as X -> 2Y which change the size of the population. This reaction can be viewed as computing the function f(x) = 2x, treating species X as input and Y as output. An additional output oblivious constraint, where the output species cannot be the input to any further reactions, enables these CRNs to be easily composed. We exactly characterize which integer-valued functions f:N^d->N can be computed by these output oblivious CRNs.