Title: Tight Analysis for the 3-Majority Consensus Dynamics,
Abstract: We present a tight analysis for the well-studied randomized 3-majority
dynamics of stabilizing consensus, hence answering the main open question of
Becchetti et al. [SODA'16].
Consider a distributed system of n nodes, each initially holding an opinion
in {1, 2, ..., k}. The system should converge to a setting where all
(non-corrupted) nodes hold the same opinion. This consensus opinion should be
\emph{valid}, meaning that it should be among the initially supported opinions,
and the (fast) convergence should happen even in the presence of a malicious
adversary who can corrupt a bounded number of nodes per round and in particular
modify their opinions. A well-studied distributed algorithm for this problem is
the 3-majority dynamics, which works as follows: per round, each node gathers
three opinions --- say by taking its own and two of other nodes sampled at
random --- and then it sets its opinion equal to the majority of this set; ties
are broken arbitrarily, e.g., towards the node's own opinion.
Becchetti et al. [SODA'16] showed that the 3-majority dynamics converges to
consensus in O((k^2\sqrt{\log n} + k\log n)(k+\log n)) rounds, even in the
presence of a limited adversary. We prove that, even with a stronger adversary,
the convergence happens within O(k\log n) rounds. This bound is known to be
optimal.