Abstract
Population protocols are a model for distributed computing in which n agents with limited computational power and memory perform randomly scheduled pairwise interactions. Despite – or rather because of – its simplicity, this model has gained a lot of attention during the past 8 years. Applications range from modeling behavior in animal populations over representing an important special case of chemical reaction networks to some natural population protocols being equivalent to computational tasks performed by, for example, living cells.
A fundamental problem in this setting is plurality consensus, where all agents start with one of k opinions and the goal is for each agent to learn which is the initial most frequent opinion. The case of k=2 opinions is known as the majority problem. Recent breakthroughs led to an always correct majority population protocol that is both time- and space-optimal, requiring O(log(n)) states per agent and, w.h.p., O(log(n)) time [Doty et al.; FOCS '21]. Meanwhile, results for general plurality consensus are scarce and far from optimal. We know that any always correct protocol requires Omega(k2) states, while the currently best general protocol needs O(k11) states [Natale and Ramezani; 2019].
In this talk, I present a plurality consensus protocol [Berenbrink et al.; PODC '22] that beats the quadratic lower bound by allowing a negligible failure probability. While our protocol might fail, it identifies the plurality opinion with high probability even if the bias is 1. This complements another of our recent results [Berenbrink et al.; SODA'22], which gives protocol with subquadratic states that is always correct if the difference between the largest and second-largest opinion is large enough but might fail otherwise.