---
res:
  bibo_abstract:
  - "In the stochastic population protocol model, we are given a connected graph with
    n nodes, and in every time step, a scheduler samples an edge of the graph uniformly
    at random and the nodes connected by this edge interact. A fundamental task in
    this model is stable leader election, in which all nodes start in an identical
    state and the aim is to reach a configuration in which (1)\r\nexactly one node
    is elected as leader and (2) this node remains as the unique leader no matter
    what sequence of interactions follows. On cliques, the complexity of this problem
    has recently been settled: time-optimal protocols stabilize in (n log n) expected
    steps using (log log n) states, whereas protocols that use O(1) states require
    (n2) expected steps. In this work, we investigate the complexity of stable leader
    election on graphs. We provide the first non-trivial time lower bounds on general
    graphs, showing that, when moving beyond cliques, the complexity of stable leader
    election can range from O(1) to (n3) expected steps. We describe a protocol that
    is time-optimal on many graph families, but uses polynomially-many states. In
    contrast, we give a near-time-optimal protocol that uses only O(log2 n) states
    that is at most a factor O(log n) slower. Finally, we observe that for many graphs
    the constant-state protocol of Beauquier et al. [OPODIS 2013] is at most a factor
    O(n log n) slower than the fast polynomial-state protocol, and among constant-state
    protocols, this protocol has near-optimal average case complexity on dense random
    graphs.@eng"
  bibo_authorlist:
  - foaf_Person:
      foaf_givenName: Dan-Adrian
      foaf_name: Alistarh, Dan-Adrian
      foaf_surname: Alistarh
      foaf_workInfoHomepage: http://www.librecat.org/personId=4A899BFC-F248-11E8-B48F-1D18A9856A87
    orcid: 0000-0003-3650-940X
  - foaf_Person:
      foaf_givenName: Joel
      foaf_name: Rybicki, Joel
      foaf_surname: Rybicki
      foaf_workInfoHomepage: http://www.librecat.org/personId=334EFD2E-F248-11E8-B48F-1D18A9856A87
    orcid: 0000-0002-6432-6646
  - foaf_Person:
      foaf_givenName: Sasha
      foaf_name: Voitovych, Sasha
      foaf_surname: Voitovych
  bibo_doi: 10.1007/s00446-025-00487-7
  bibo_volume: 38
  dct_date: 2025^xs_gYear
  dct_identifier:
  - UT:001518300400001
  dct_isPartOf:
  - http://id.crossref.org/issn/0178-2770
  - http://id.crossref.org/issn/1432-0452
  dct_language: eng
  dct_publisher: Springer Nature@
  dct_title: Near-optimal leader election in population protocols on graphs@
...