Plurality consensus in arbitrary graphs : lessons learned from load balancing.
From MaRDI portal
Publication:4606279
DOI10.4230/LIPICS.ESA.2016.10zbMATH Open1397.68014arXiv1602.01342OpenAlexW2546217121MaRDI QIDQ4606279FDOQ4606279
Peter Kling, Chris Wastell, Frederik Mallmann-Trenn, Petra Berenbrink, Tom Friedetzky
Publication date: 2 March 2018
Abstract: We consider emph{plurality consensus} in a network of nodes. Initially, each node has one of opinions. The nodes execute a (randomized) distributed protocol to agree on the plurality opinion (the opinion initially supported by the most nodes). Nodes in such networks are often quite cheap and simple, and hence one seeks protocols that are not only fast but also simple and space efficient. Typically, protocols depend heavily on the employed communication mechanism, which ranges from sequential (only one pair of nodes communicates at any time) to fully parallel (all nodes communicate with all their neighbors at once) communication and everything in-between. We propose a framework to design protocols for a multitude of communication mechanisms. We introduce protocols that solve the plurality consensus problem and are with probability 1-o(1) both time and space efficient. Our protocols are based on an interesting relationship between plurality consensus and distributed load balancing. This relationship allows us to design protocols that generalize the state of the art for a large range of problem parameters. In particular, we obtain the same bounds as the recent result of Alistarh et al. (who consider only two opinions on a clique) using a much simpler protocol that generalizes naturally to general graphs and multiple opinions.
Full work available at URL: https://arxiv.org/abs/1602.01342
Cited In (2)
This page was built for publication: Plurality consensus in arbitrary graphs : lessons learned from load balancing.
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4606279)
