What does this research mean for the field?

The Circles protocol solves the relative majority problem in population protocols using k^3 states, improving upon the previous upper bound of O(k^7). Novelty: ClaimNovelty.NOVEL_FINDING. Consensus alignment: ConsensusAlignment.CHALLENGES_CONSENSUS.

What question did this study set out to answer?

The aim is to address the relative majority problem in the population protocol model using a new protocol.

February 25, 2026Open Access

Brief announcement: Minimizing energy solves relative majority with a cubic number of states in population protocols

Key Points

The aim is to address the relative majority problem in the population protocol model using a new protocol.
Introduced the Circles protocol as a solution for the relative majority problem
Implemented under weakly fair scheduling conditions
Utilized energy minimization principles from chemical settings
The Circles protocol uses k3 states, significantly fewer than the previous best of O(k7)
Demonstrated always-correct performance under specified scheduling
Showed a simpler design compared to existing solutions

Abstract

This paper revisits a fundamental distributed computing problem in the population protocol model. Provided n agents each starting with an input color in k, the relative majority problem asks to find the predominant color. In the population protocol model, at each time step, a scheduler selects two agents that first learn each other's states and then update their states based on what they learned. We present the Circles protocol that solves the relative majority problem with k3 states. It is always-correct under weakly fair scheduling. Not only does it improve upon the best known upper bound of O(k7), but it also shows a strikingly simpler design inspired by energy minimization in chemical settings.

Bookmark

View Full Paper