On the hierarchy of distributed majority protocols

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].

Subjects

Consensus

Gossip Model

Hierarchy

Majority

Population Protocols

Stochastic Dominance

Strassen’s Theorem

DDC Class

004: Informatik

600: Technik

Publication version

publishedVersion

Lizenz

https://creativecommons.org/licenses/by/4.0/

Name

LIPIcs-OPODIS-2022-23.pdf

Size

885.65 KB

Format

Adobe PDF

Options

On the hierarchy of distributed majority protocols