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
| CREATOR | Henry Austin, Petra Berenbrink, Tom Friedetzky, Thorsten Götte, Lukas Hintze |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 136 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-01210