Skip to main content

Research Repository

Advanced Search

Plurality Consensus in Arbitrary Graphs: Lessons Learned from Load Balancing

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

Plurality Consensus in Arbitrary Graphs: Lessons Learned from Load Balancing Thumbnail


Authors

Petra Berenbrink

Peter Kling

Frederik Mallmann-Trenn

Chris Wastell



Contributors

Piotr Sankowski
Editor

Christos Zaroliagis
Editor

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.

Citation

Berenbrink, P., Friedetzky, T., Kling, P., Mallmann-Trenn, F., & Wastell, C. (2016). Plurality Consensus in Arbitrary Graphs: Lessons Learned from Load Balancing. In P. Sankowski, & C. Zaroliagis (Eds.), 24th Annual European Symposium on Algorithms (ESA 2016) (1-18). https://doi.org/10.4230/lipics.esa.2016.10

Conference Name 24th Annual European Symposium on Algorithms (ESA 2016)
Conference Location Aarhus, Denmark
Acceptance Date Jun 9, 2016
Online Publication Date Aug 18, 2016
Publication Date Aug 22, 2016
Deposit Date Oct 17, 2016
Publicly Available Date Oct 21, 2016
Volume 57
Pages 1-18
Series Title Leibniz International Proceedings in Informatics (LIPIcs)
Series Number 10.4230/LIPIcs.ESA.2016.10
Series ISSN 1868-8969
Book Title 24th Annual European Symposium on Algorithms (ESA 2016).
DOI https://doi.org/10.4230/lipics.esa.2016.10
Public URL https://durham-repository.worktribe.com/output/1150119
Additional Information Don't think there is a Volume. [HE 13/11/2020] Conference date: 22-26 August 2016 Date of publication: 18.08.2016

Files





You might also like



Downloadable Citations