Talley Amir, James Aspnes, Petra Berenbrink, Felix Biermeier, Christopher Hahn, Dominik Kaaser, and John Lazarsfeld. Fast convergence of k-undecided state dynamics in the population protocol model. 2023 ACM Symposium on Principles of Distributed Computing, June 2023, pp. 13–23.
We analyze the convergence of the k-opinion Undecided State Dynamics (USD) in the population protocol model. For k=2 opinions it is well known that the USD reaches consensus with high probability within O(n log n) interactions. Proving that the process also quickly solves the consensus problem for k > 2 opinions has remained open, despite analogous results for larger k in the related parallel gossip model. In this paper we prove such convergence: under mild assumptions on k and on the initial number of undecided agents we prove that the USD achieves plurality consensus within O(k n log n) interactions with high probability, regardless of the initial bias. Moreover, if there is an initial additive bias of at least Ω(√n log n), we prove that the initial plurality opinion wins with high probability, and if there is a multiplicative bias the convergence time is further improved. Note that this is the first result for k>2 for the USD in the population protocol model. Furthermore, it is the first result for the unsynchronized variant of the USD with k>2 which does not need any initial bias.
@inproceedings{AmirABBHKL2023,
author = {Talley Amir and
James Aspnes and
Petra Berenbrink and
Felix Biermeier and
Christopher Hahn and
Dominik Kaaser and
John Lazarsfeld},
editor = {Rotem Oshman and
Alexandre Nolin and
Magn{\'{u}}s M. Halld{\'{o}}rsson and
Alkida Balliu},
title = {Fast Convergence of k-Opinion Undecided State Dynamics in the Population
Protocol Model},
booktitle = {Proceedings of the 2023 {ACM} Symposium on Principles of Distributed
Computing, {PODC} 2023, Orlando, FL, USA, June 19-23, 2023},
pages = {13--23},
publisher = {{ACM}},
year = {2023},
url = {https://doi.org/10.1145/3583668.3594589},
doi = {10.1145/3583668.3594589},
timestamp = {Mon, 19 Jun 2023 08:58:36 +0200},
biburl = {https://dblp.org/rec/conf/podc/AmirABBHKL23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}