2026-07-22T19:10:15Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17643 2024-03-06T11:00:12Z ddc:004 open_access

On the Hierarchy of Distributed Majority Protocols Berenbrink, Petra Coja-Oghlan, Amin Gebhard, Oliver Hahn-Klimroth, Max Kaaser, Dominik Rau, Malin Consensus Majority Hierarchy Stochastic Dominance Population Protocols Gossip Model Strassen’s Theorem We study the consensus problem among n agents, defined as follows. Initially, each agent holds one of two possible opinions. The goal is to reach a consensus configuration in which every agent shares the same opinion. To this end, agents randomly sample other agents and update their opinion according to a simple update function depending on the sampled opinions. We consider two communication models: the gossip model and a variant of the population model. In the gossip model, agents are activated in parallel, synchronous rounds. In the population model, one agent is activated after the other in a sequence of discrete time steps. For both models we analyze the following natural family of majority processes called j-Majority: when activated, every agent samples j other agents uniformly at random (with replacement) and adopts the majority opinion among the sample (breaking ties uniformly at random). As our main result we show a hierarchy among majority protocols: (j+1)-Majority (for j > 1) converges stochastically faster than j-Majority for any initial opinion configuration. In our analysis we use Strassen’s Theorem to prove the existence of a coupling. This gives an affirmative answer for the case of two opinions to an open question asked by Berenbrink et al. [PODC 2017]. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Petra Berenbrink and Amin Coja-Oghlan and Oliver Gebhard and Max Hahn-Klimroth and Dominik Kaaser and Malin Rau 2023 Is Part Of LIPIcs, Volume 253, 26th International Conference on Principles of Distributed Systems (OPODIS 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.OPODIS.2022.23 urn:nbn:de:0030-drops-176434 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2022.23 eng https://creativecommons.org/licenses/by/4.0/legalcode