



























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 \textsc{Circles} protocol that solves the relative majority problem with $k^3$ states. It is always-correct under weakly fair scheduling. Not only does it improve upon the best known upper bound of $O(k^7)$, but it also shows a strikingly simpler design inspired by energy minimization in chemical settings.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。