License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2016.10
URN: urn:nbn:de:0030-drops-63610
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6361/
Go to the corresponding LIPIcs Volume Portal

Berenbrink, Petra ; Friedetzky, Tom ; Kling, Peter ; Mallmann-Trenn, Frederik ; Wastell, Chris

Plurality Consensus in Arbitrary Graphs: Lessons Learned from Load Balancing

pdf-format:
LIPIcs-ESA-2016-10.pdf (0.7 MB)

Abstract

We consider plurality consensus in networks of n nodes. Initially, each node has one of k opinions. The nodes execute a (randomized) distributed protocol to agree on the plurality opinion (the opinion initially supported by the most nodes). In certain types of networks the nodes can be quite cheap and simple, and hence one seeks protocols that are not only time efficient 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) 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.

BibTeX - Entry

@InProceedings{berenbrink_et_al:LIPIcs:2016:6361,
  author =	{Petra Berenbrink and Tom Friedetzky and Peter Kling and Frederik Mallmann-Trenn and Chris Wastell},
  title =	{{Plurality Consensus in Arbitrary Graphs: Lessons Learned from Load Balancing}},
  booktitle =	{24th Annual European Symposium on Algorithms (ESA 2016)},
  pages =	{10:1--10:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-015-6},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{57},
  editor =	{Piotr Sankowski and Christos Zaroliagis},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6361},
  URN =		{urn:nbn:de:0030-drops-63610},
  doi =		{10.4230/LIPIcs.ESA.2016.10},
  annote =	{Keywords: Plurality Consensus, Distributed Computing, Load Balancing}
}

Keywords: Plurality Consensus, Distributed Computing, Load Balancing
Collection: 24th Annual European Symposium on Algorithms (ESA 2016)
Issue Date: 2016
Date of publication: 18.08.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI