Berenbrink, PetraPetraBerenbrinkCoja-Oghlan, AminAminCoja-OghlanGebhard, OliverOliverGebhardHahn-Klimroth, MaxMaxHahn-KlimrothKaaser, DominikDominikKaaserRau, MalinMalinRau2023-03-222023-03-222022-1226th International Conference on Principles of Distributed Systems (OPODIS 2022)http://hdl.handle.net/11420/15038We 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].enhttps://creativecommons.org/licenses/by/4.0/ConsensusGossip ModelHierarchyMajorityPopulation ProtocolsStochastic DominanceStrassen’s TheoremInformatikTechnikConference Paper10.15480/882.501510.4230/LIPIcs.OPODIS.2022.2310.15480/882.5015Conference Paper