A population protocol is a distributed computing model formed by resource-limited mobile agents which meet in a random way according to an interaction graph.
Functions are computed by updating the state of agents whenever they meet based on their previous state, and the result of the computation can be read in the states of the agents once the computation has converged.
An important class of population protocols are majority algorithms, where the goal is to compute the majority bit: each node starts with a belief bit in
and the goal is to design a protocol at the end of which the belief bit of every node is the correct initial majority bit.
The discrete time version of the model is as follows: at each point
, which is chosen uniformly at random from the set of neighbors of node
exchange memory contents and update their states.
Alternatively, one can consider a continuous time model where each node
has a Poisson clock that rings at unit rate.
Protocols are often designed to minimize the convergence time or the amount of memory required per node or both.
[1] For the problem of computing the majority (consensus), there is a well-known protocol that requires only three memory states per node and has been analyzed for complete interaction graphs.
At each point in time, when two nodes communicate, they update their state according to the following table.
The row labels give the initiator’s state and the column labels the responder’s state.
In words, if a node with belief
Note that this protocol is one-way: every interaction changes at most the responder’s state; thus it can be implemented with one-way communication.
Angluin, Aspnes, and Eisenstat [2] showed that, from any initial configuration that does not consist of all "
"s, the three-state approximate majority protocol converges to either all nodes having belief
Additionally, the value chosen will be the majority non-"
" initial value, provided it exceeds the minority by a sufficient margin.
The following picture shows the evolution of the three state protocol on a set of
, while the remaining two thirds have initial belief bit
" nodes (in orange) starts at zero, increases for a while, and then goes again to zero.
Population protocols were introduced by Dana Angluin et al.[4] as one of the first models of computation to be fully decentralized and to involve agents with highly limited resources, e.g., those found in sensor networks.
Since then, this abstract computation model found applications in robotics[5] and chemistry.