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

CREATORTom-Lukas Breitkopf, Julien Dallot, Antoine El-Hayek, Stefan Schmid
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE17 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

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

Browse the full library · About the Tower of Babel