---
_id: '7123'
abstract:
- lang: eng
  text: "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.\r\n\r\nOn 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."
article_processing_charge: No
arxiv: 1
author:
- first_name: Dan-Adrian
  full_name: Alistarh, Dan-Adrian
  id: 4A899BFC-F248-11E8-B48F-1D18A9856A87
  last_name: Alistarh
  orcid: 0000-0003-3650-940X
- first_name: James
  full_name: Aspnes, James
  last_name: Aspnes
- first_name: Rati
  full_name: Gelashvili, Rati
  last_name: Gelashvili
citation:
  ama: 'Alistarh D-A, Aspnes J, Gelashvili R. Space-optimal majority in population
    protocols. In: <i>Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete
    Algorithms</i>. ACM; 2018:2221-2239. doi:<a href="https://doi.org/10.1137/1.9781611975031.144">10.1137/1.9781611975031.144</a>'
  apa: 'Alistarh, D.-A., Aspnes, J., &#38; Gelashvili, R. (2018). Space-optimal majority
    in population protocols. In <i>Proceedings of the 29th Annual ACM-SIAM Symposium
    on Discrete Algorithms</i> (pp. 2221–2239). New Orleans, LA, United States: ACM.
    <a href="https://doi.org/10.1137/1.9781611975031.144">https://doi.org/10.1137/1.9781611975031.144</a>'
  chicago: Alistarh, Dan-Adrian, James Aspnes, and Rati Gelashvili. “Space-Optimal
    Majority in Population Protocols.” In <i>Proceedings of the 29th Annual ACM-SIAM
    Symposium on Discrete Algorithms</i>, 2221–39. ACM, 2018. <a href="https://doi.org/10.1137/1.9781611975031.144">https://doi.org/10.1137/1.9781611975031.144</a>.
  ieee: D.-A. Alistarh, J. Aspnes, and R. Gelashvili, “Space-optimal majority in population
    protocols,” in <i>Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete
    Algorithms</i>, New Orleans, LA, United States, 2018, pp. 2221–2239.
  ista: '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.'
  mla: Alistarh, Dan-Adrian, et al. “Space-Optimal Majority in Population Protocols.”
    <i>Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms</i>,
    ACM, 2018, pp. 2221–39, doi:<a href="https://doi.org/10.1137/1.9781611975031.144">10.1137/1.9781611975031.144</a>.
  short: D.-A. Alistarh, J. Aspnes, R. Gelashvili, in:, Proceedings of the 29th Annual
    ACM-SIAM Symposium on Discrete Algorithms, ACM, 2018, pp. 2221–2239.
conference:
  end_date: 2018-01-10
  location: New Orleans, LA, United States
  name: 'SODA: Symposium on Discrete Algorithms'
  start_date: 2018-01-07
date_created: 2019-11-26T15:10:55Z
date_published: 2018-01-30T00:00:00Z
date_updated: 2023-09-19T15:03:16Z
day: '30'
department:
- _id: DaAl
doi: 10.1137/1.9781611975031.144
external_id:
  arxiv:
  - '1704.04947'
  isi:
  - '000483921200145'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/1704.04947
month: '01'
oa: 1
oa_version: Preprint
page: 2221-2239
publication: Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms
publication_identifier:
  isbn:
  - '9781611975031'
publication_status: published
publisher: ACM
quality_controlled: '1'
status: public
title: Space-optimal majority in population protocols
type: conference
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
year: '2018'
...