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.

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. There is a set N = \{1, 2, \ldots, 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=1,2,\ldots 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 set of neighbors of node i . Afterwards, nodes i and j exchange memory contents and update their states. 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. Protocols are often designed to minimize the convergence time or the amount of memory required per node or both. The following picture shows the evolution of the three state protocol on a set of n=500 nodes, where one third of the nodes have initial belief bit 0 , while the remaining two thirds have initial belief bit 1 . The fraction of " ? " nodes (in orange) starts at zero, increases for a while, and then goes again to zero. The three-state protocol solves the approximate majority problem, in which the correct answer is reached only with high probability and only when the initial imbalance is large enough. A harder variant is exact majority, where the population must stabilize on the true majority value with probability 1 regardless of how small the initial bias is. On complete interaction graphs, exact majority exhibits space–time trade-offs: any constant-state protocol is comparatively slow, while protocols using states can stabilize in the asymptotically optimal time. A simple four-state protocol solves exact majority on any connected interaction graph, not only complete ones. For general graphs, the time and space complexity of exact majority can be analyzed in terms of the relaxation time of the random walk induced by the scheduler and the graph's degree imbalance; on regular expander graphs this yields protocols matching the -state, near-optimal-time performance known for complete graphs. ==See also== Swarm Intelligence

Text derived from https://en.wikipedia.org/w/index.php?oldid=1369231276 under CC BY-SA 4.0; modifications have been made.