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

CREATORRobin Vacus, Isabella Ziccardi
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE55 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2502-12697

Browse the full library · About the Tower of Babel