Population protocol

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.

Formal model: there is a set N = {1,...,n} of nodes. Each node is a finite automaton with s states. 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 {0, 1} 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 t in time, some node i is selected uniformly at random. Then the node is matched with another node j, which is chosen uniformly at random from the neighborhood of node i. Afterwards, nodes i and j exchange state. Alternatively, one can consider a continuous time model where each node i has a Poisson clock that rings at unit rate. When the clock of a node rings, that node communicates with a random neighbor.

Population protocols were introduced by Dana Angluin et al. 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 and chemistry.

See also

Swarm Intelligence