2026-07-24T06:45:42Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6361 2024-03-06T10:38:03Z ddc:004 open_access

Plurality Consensus in Arbitrary Graphs: Lessons Learned from Load Balancing Berenbrink, Petra Friedetzky, Tom Kling, Peter Mallmann-Trenn, Frederik Wastell, Chris Plurality Consensus Distributed Computing Load Balancing 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Petra Berenbrink and Tom Friedetzky and Peter Kling and Frederik Mallmann-Trenn and Chris Wastell 2016 Is Part Of LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2016.10 urn:nbn:de:0030-drops-63610 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.10 eng https://creativecommons.org/licenses/by/3.0/legalcode