Brief Announcement: Minimizing Energy Solves Relative Majority with a Cubic Number of States in Population Protocols
Tom-Lukas Breitkopf, Julien Dallot, Antoine El-Hayek, Stefan Schmid · 2025
Read Brief Announcement: Minimizing Energy Solves Relative Majority with a Cubic Number of States in Population Protocols by Tom-Lukas Breitkopf, Julien Dallot, Antoine El-Hayek, Stefan Schmid (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-02785.txt.
Description
Tom-Lukas Breitkopf and co-authors revisit majority finding in population protocols, in a 2025 paper. In this model, many simple agents meet in pairs, learn each other's state, and update. Each agent starts with one of several colors, and the group must find the most common color.
Their protocol, called Circles, solves the relative majority problem with far fewer states than the past best bound. It is always correct under a fair schedule of meetings. The design is also simpler than past ones and draws on energy minimization in chemistry. The result tightens a basic bound in distributed computing with a clean idea.
Catalog record
| CREATOR | Tom-Lukas Breitkopf, Julien Dallot, Antoine El-Hayek, Stefan Schmid |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 17 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-02785