Minimalist Leader Election Under Weak Communication
Robin Vacus, Isabella Ziccardi · 2025
Read Minimalist Leader Election Under Weak Communication by Robin Vacus, Isabella Ziccardi (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-2502-12697.txt.
Description
Robin Vacus and Isabella Ziccardi design a leader election protocol for networks that can barely communicate, in a 2025 paper. In the beeping model, nodes can only beep or listen; in the stone-age model, they are nearly as limited. Their protocol uses just six internal states per node, needs no unique names, and assumes no knowledge of the network's size or shape. Under it, the system almost surely ends with exactly one node in the leader state.
That outcome arrives quickly with high probability, within a bound tied to the network's diameter. Knowing a rough diameter estimate speeds it further. The trade-offs are a slower finish than protocols with stronger assumptions, and nodes never learn that the election ended. The appeal is minimalism: election with almost nothing.
Catalog record
| CREATOR | Robin Vacus, Isabella Ziccardi |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 55 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2502-12697