# Space-optimal majority in population protocols

D.-A. Alistarh, J. Aspnes, R. Gelashvili, in:, Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms, ACM, 2018, pp. 2221–2239.

Download (ext.)

*Conference Paper*|

*Published*|

*English*

Author

Department

Abstract

Population protocols are a popular model of distributed computing, in which n agents with limited local state interact randomly, and cooperate to collectively compute global predicates. Inspired by recent developments in DNA programming, an extensive series of papers, across different communities, has examined the computability and complexity characteristics of this model. Majority, or consensus, is a central task in this model, in which agents need to collectively reach a decision as to which one of two states A or B had a higher initial count. Two metrics are important: the time that a protocol requires to stabilize to an output decision, and the state space size that each agent requires to do so. It is known that majority requires Ω(log log n) states per agent to allow for fast (poly-logarithmic time) stabilization, and that O(log2 n) states are sufficient. Thus, there is an exponential gap between the space upper and lower bounds for this problem. This paper addresses this question.
On the negative side, we provide a new lower bound of Ω(log n) states for any protocol which stabilizes in O(n1–c) expected time, for any constant c > 0. This result is conditional on monotonicity and output assumptions, satisfied by all known protocols. Technically, it represents a departure from previous lower bounds, in that it does not rely on the existence of dense configurations. Instead, we introduce a new generalized surgery technique to prove the existence of incorrect executions for any algorithm which would contradict the lower bound. Subsequently, our lower bound also applies to general initial configurations, including ones with a leader. On the positive side, we give a new algorithm for majority which uses O(log n) states, and stabilizes in O(log2 n) expected time. Central to the algorithm is a new leaderless phase clock technique, which allows agents to synchronize in phases of Θ(n log n) consecutive interactions using O(log n) states per agent, exploiting a new connection between population protocols and power-of-two-choices load balancing mechanisms. We also employ our phase clock to build a leader election algorithm with a state space of size O(log n), which stabilizes in O(log2 n) expected time.

Publishing Year

Date Published

2018-01-30

Proceedings Title

Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms

Page

2221-2239

Conference

SODA: Symposium on Discrete Algorithms

Conference Location

New Orleans, LA, United States

Conference Date

2018-01-07 – 2018-01-10

ISBN

IST-REx-ID

### Cite this

Alistarh D-A, Aspnes J, Gelashvili R. Space-optimal majority in population protocols. In:

*Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms*. ACM; 2018:2221-2239. doi:10.1137/1.9781611975031.144Alistarh, D.-A., Aspnes, J., & Gelashvili, R. (2018). Space-optimal majority in population protocols. In

*Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms*(pp. 2221–2239). New Orleans, LA, United States: ACM. https://doi.org/10.1137/1.9781611975031.144Alistarh, Dan-Adrian, James Aspnes, and Rati Gelashvili. “Space-Optimal Majority in Population Protocols.” In

*Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms*, 2221–39. ACM, 2018. https://doi.org/10.1137/1.9781611975031.144.D.-A. Alistarh, J. Aspnes, and R. Gelashvili, “Space-optimal majority in population protocols,” in

*Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms*, New Orleans, LA, United States, 2018, pp. 2221–2239.Alistarh D-A, Aspnes J, Gelashvili R. 2018. Space-optimal majority in population protocols. Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms 2221–2239.

Alistarh, Dan-Adrian, et al. “Space-Optimal Majority in Population Protocols.”

*Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms*, ACM, 2018, pp. 2221–39, doi:10.1137/1.9781611975031.144.### Export

Marked PublicationsOpen Data IST Research Explorer

### Sources

arXiv 1704.04947