A Space-Time Trade-off for Fast Self-Stabilizing Leader Election in Population Protocols

Henry Austin, Petra Berenbrink, Tom Friedetzky, Thorsten Götte, Lukas Hintze · 2025

Read A Space-Time Trade-off for Fast Self-Stabilizing Leader Election in Population Protocols by Henry Austin, Petra Berenbrink, Tom Friedetzky, Thorsten Götte, Lukas Hintze (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-01210.txt.

Description

Henry Austin, Petra Berenbrink, and their co-authors study how a large group of simple agents can pick a single leader on its own. Their 2025 paper uses the population model, where pairs of agents meet at random and swap simple states. The group must settle on one leader starting from any state at all, a trait called self stabilization.

The hard part is speed versus memory: fast methods tend to need huge numbers of states per agent. The authors give a flexible method that, with the right setting, reaches the best known time while using far fewer states than the prior best fast method. Their counts rest on a trade off curve, so users can pick a balance between time and states. The result matters for models of tiny devices and natural swarms.

Catalog record

CREATORHenry Austin, Petra Berenbrink, Tom Friedetzky, Thorsten Götte, Lukas Hintze
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE136 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-01210

Browse the full library · About the Tower of Babel