conference paper published yes Tom-Lukas Breitkopf author Julien Dallot author Antoine El-Hayek author 888a098e-fcac-11ee-aff7-d347be57b7250000-0003-4268-7368 Stefan Schmid author MoHe department PODC: Symposium on Principles of Distributed Computing The design and evaluation of modern fully dynamic data structures project Static and Dynamic Hierarchical Graph Decompositions project Fast Algorithms for a Reactive Network Layer project 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. https://research-explorer.ista.ac.at/download/20052/20123/2025_PODC_Breitkopf.pdf application/pdfno Association for Computing Machinery2025Huatulco, Mexico eng 9798400718854 00152553480006910.1145/3732772.3733512 549-552 T.-L. Breitkopf, J. Dallot, A. El-Hayek, and S. Schmid, “Brief announcement: Minimizing energy solves relative majority with a cubic number of states in population protocols,” in <i>Proceedings of the ACM Symposium on Principles of Distributed Computing</i>, Huatulco, Mexico, 2025, pp. 549–552. Breitkopf, Tom-Lukas, et al. “Brief Announcement: Minimizing Energy Solves Relative Majority with a Cubic Number of States in Population Protocols.” <i>Proceedings of the ACM Symposium on Principles of Distributed Computing</i>, Association for Computing Machinery, 2025, pp. 549–52, doi:<a href="https://doi.org/10.1145/3732772.3733512">10.1145/3732772.3733512</a>. Breitkopf, T.-L., Dallot, J., El-Hayek, A., &#38; Schmid, S. (2025). Brief announcement: Minimizing energy solves relative majority with a cubic number of states in population protocols. In <i>Proceedings of the ACM Symposium on Principles of Distributed Computing</i> (pp. 549–552). Huatulco, Mexico: Association for Computing Machinery. <a href="https://doi.org/10.1145/3732772.3733512">https://doi.org/10.1145/3732772.3733512</a> Breitkopf T-L, Dallot J, El-Hayek A, Schmid S. Brief announcement: Minimizing energy solves relative majority with a cubic number of states in population protocols. In: <i>Proceedings of the ACM Symposium on Principles of Distributed Computing</i>. Association for Computing Machinery; 2025:549-552. doi:<a href="https://doi.org/10.1145/3732772.3733512">10.1145/3732772.3733512</a> T.-L. Breitkopf, J. Dallot, A. El-Hayek, S. Schmid, in:, Proceedings of the ACM Symposium on Principles of Distributed Computing, Association for Computing Machinery, 2025, pp. 549–552. Breitkopf T-L, Dallot J, El-Hayek A, Schmid S. 2025. Brief announcement: Minimizing energy solves relative majority with a cubic number of states in population protocols. Proceedings of the ACM Symposium on Principles of Distributed Computing. PODC: Symposium on Principles of Distributed Computing, 549–552. Breitkopf, Tom-Lukas, Julien Dallot, Antoine El-Hayek, and Stefan Schmid. “Brief Announcement: Minimizing Energy Solves Relative Majority with a Cubic Number of States in Population Protocols.” In <i>Proceedings of the ACM Symposium on Principles of Distributed Computing</i>, 549–52. Association for Computing Machinery, 2025. <a href="https://doi.org/10.1145/3732772.3733512">https://doi.org/10.1145/3732772.3733512</a>. 200522025-07-21T08:17:04Z2026-02-16T11:46:37Z