Population Protocols for Exact Plurality Consensus
Gregor Bankhamer, Petra Berenbrink, Felix Biermeier, Robert Elsässer⋆, Hamed Hosseinpour, Dominik Kaaser, Peter Kling · 2022
We consider the plurality consensus problem for population protocols. Here, n anonymous agents start each with one of k opinions. Their goal is to agree on the initially most frequent opinion (the plurality opinion) via random, pairwise interactions. Exact plurality consensus refers to the requirement that the plurality opinion must be identified even if the bias (difference between the most and second most frequent opinion) is only 1.