Plurality Consensus in Arbitrary Graphs: Lessons Learned from Load Balancing

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

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, August). Plurality Consensus in Arbitrary Graphs: Lessons Learned from Load Balancing. Presented at 24th Annual European Symposium on Algorithms (ESA 2016), Aarhus, Denmark

• Presentation Conference Type: Conference Paper (published)
• Conference Name: 24th Annual European Symposium on Algorithms (ESA 2016)
• 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