PLACE: FAMNIT-Muzejski3 at 16:00

LECTURER: Prof. Dr. Robert Elsässer

ABSTRACT:
We consider the problem of distributed plurality consensus. In the most basic two-choices process we are given a complte graph in which initially every node holds one of $k$ different opinions. In each (synchronous) step, every node chooses two neighbors uniformly at random. If the opinions of the two neighbors coincide, then this opinion is adopted.

We show that if $k =O(n^\epsilon)$ for some small $\epsilon$, then this protocol converges to the initial majority within $O(k \cdot \log{n})$ steps, with high probability, as long as the initial difference between the largest and second largest opinion is $\Omega(\sqrt{n \log n})$. This upper bound holds even in the presence of an adversary who can change up to $O(\sqrt{n\log n}/k)$ nodes per round. The required initial difference is tight up to a factor of $\sqrt{\log{n}}$ even in absence of an adversary, in the following sense: If the difference is only $O(\sqrt{n})$, then the largest opinion may lose the vote with constant probability.

Furthrmore, we consider simple modifications of the two-choices protocol in order to speed up the process in the synchronous model, and extend one of the results to an asynchronous setting described by a sequential communication model, in which only one randomly chosen node performs at most two queries per step.

Welcome!