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.
Model
There is a set Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle N = \{1, 2, \ldots, n\}} of nodes. Each node is a finite automaton with 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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \{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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle t=1,2,\ldots} in time, some node Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i} is selected uniformly at random. Then the node is matched with another node Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle j} , which is chosen uniformly at random from the set of neighbors of node Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i} . Afterwards, nodes and 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. 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.[1]
Three State Protocol
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.[2][3] This protocol works as follows. Let each node initialize its memory state to their initial belief bit 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.
| 0 | ? | 1 | |
|---|---|---|---|
| 0 | (0,0) | (0,0) | (0,?) |
| ? | (?,0) | (?,?) | (?,1) |
| 1 | (1,?) | (1,1) | (1,1) |
In words, if a node with belief gets matched with a node with belief , then both nodes keep their belief; the update is similar if both beliefs are or both are . However, if the initiator's belief is Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0} and the responder's belief is Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle ?} , then the respondent updates their belief to Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0} . If on the other hand the initiator has belief Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0} and the responder has belief Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1} , then the responder changes their belief to Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle ?} . 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 "Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle ?} "s, the three-state approximate majority protocol converges to either all nodes having belief Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0} or all nodes having belief within Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(n \cdot \log n)} interactions with high probability. Additionally, the value chosen will be the majority non-"Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle ?} " 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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n=500} nodes, where one third of the nodes have initial belief bit Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0} , while the remaining two thirds have initial belief bit Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1} . The fraction of "Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle ?} " nodes (in orange) starts at zero, increases for a while, and then goes again to zero.
History
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.[6]
See also
References
- ^ Alistarh, Dan; Aspnes, James; Eisenstat, David; Gelashvili, Rati; Rivest, Ronald L. (2017-01-16). "Time-space trade-offs in population protocols". Soda '17. Society for Industrial and Applied Mathematics: 2560–2579. arXiv:1602.08032. Bibcode:2016arXiv160208032A.
{{cite journal}}: Cite journal requires|journal=(help) - ^ 2.0 2.1 Angluin, Dana; Aspnes, James; Eisenstat, David (2007), "A Simple Population Protocol for Fast Robust Approximate Majority", Distributed Computing, Lecture Notes in Computer Science, vol. 4731, Springer Berlin Heidelberg, pp. 20–32, CiteSeerX 10.1.1.80.828, doi:10.1007/978-3-540-75142-7_5, ISBN 9783540751410
- ^ Perron, E.; Vasudevan, D.; Vojnovic, M. (April 2009). "Using Three States for Binary Consensus on Complete Graphs". IEEE Infocom 2009. IEEE. pp. 2527–2535. doi:10.1109/infcom.2009.5062181. ISBN 9781424435128. S2CID 12683772.
- ^ Dana Angluin, James Aspnes, Zoë Diamadi, Michael J. Fischer, René Peralta. Computation in networks of passively mobile finite-state sensors. Distributed Computing, 2006. [1]
- ^ Gregory Dudek, Michael Jenkin. Computational Principles of Mobile Robotics, Chapter 10.
- ^ Ho-Lin Chen, David Doty, David Soloveichik. Deterministic function computation with chemical reaction networks. Natural Computing, 2014. [2]