We study a plurality-consensus process in which each of n anonymous agents of a communication network initially supports a color chosen from the set [k]. Then, in every round, each agent can revise his color according to the colors currently held by a random sample of his neighbors. It is assumed that the initial color configuration exhibits a sufficiently large bias s towards a fixed plurality color, that is, the number of nodes supporting the plurality color exceeds the number of nodes supporting any other color by s additional nodes. The goal is having the Partially supported by Italian MIUR-process to converge to the stable configuration in which all nodes support the initial plurality. We consider a basic model in which the network is a clique and the update rule (called here the 3-majority dynamics) of the process is the following: each agent looks at the colors of three random neighbors and then applies the majority rule (breaking ties uniformly). We prove that the process converges in time O(min{k, (n/ log n) 1/3 } log n) with high probability, provided that s c min{2k, (n/ log n) 1/3 } n log n. We then prove that our upper bound above is tight as long as k (n/ log n) 1/4 . This fact implies an exponential timegap between the plurality-consensus process and the median process (see Doerr et al. in Proceedings of the 23rd annual ACM symposium on parallelism in algorithms and architectures (SPAA'11), pp 149-158. ACM, 2011). A natural question is whether looking at more (than three) random neighbors can significantly speed up the process. We provide a negative answer to this question: in particular, we show that samples of polylogarithmic size can speed up the process by a polylogarithmic factor only.
The authors of REF assume that the bias is Ω(min{ √ 2k, (n/ log n) 1/6 } · √ n log n).
Simple dynamics for plurality consensus
Distributed Computing
Distributed Computing
Mathematics Computer Science