English      Slovensko
DIST Department of information sciences and technologies

A seminar titled "Plurality Consensus - The two choices protocol and some variants of it" will be presented by Prof. Dr. Robert Elsässer on Friday, 10. November 2017 at 16.00 at the Faculty of Mathematics, Natural Sciences and Information Technologies of the University of Primorska.


PLACE: FAMNIT-Muzejski3 at 16:00

LECTURER: Prof. Dr. Robert Elsässer

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.