A Polylogarithmic Gossip Algorithm for Plurality Consensus
Mohsen Ghaffari, Merav Parter · 2016
Consider n anonymous nodes each initially supporting an opinion in {1, 2, …, k} and suppose that they should all learn the opinion with the largest support. Per round, each node contacts a random other node and exchanges B bits with it, where typically B is at most O(log n).