Sample size and speed trade off in consensus processes
Nearly-Optimal Time-Sample Trade-off in Consensus Dynamics
Distributed, Parallel, and Cluster ComputingData Structures and Algorithms
Summary
This paper looks at how the number of opinions each member samples affects how fast a group reaches agreement. The authors study a method where each member picks a few opinions from others and then adopts the most common one they find. They prove that this method balances sampling size and agreement time nearly as well as possible for many situations. Their results hold for all sample sizes three or larger and for any starting mix of opinions. They also show when the most popular opinion has a good head start, everyone agrees quickly, and no similar method can do much better.
What this means in practice
- •For distributed systems engineers: Predict and optimize the rounds needed for distributed nodes to reach consensus based on sample sizes from peers.
- •For social network algorithm designers: Design opinion spreading protocols that efficiently balance communication overhead and speed to consensus.
A theory result. No direct application yet.
Authors
Francesco d'Amore, Joel Rybicki, Nobutaka Shimizu, Takeharu Shiraga, Robin Vacus
Abstract
How does the number of sampled opinions affect the time required to reach consensus in distributed consensus dynamics? We study the synchronous $h$-\textsf{Majority}, in which every node independently samples $h$ nodes uniformly at random with replacement in each round and adopts a most frequent sampled opinion, breaking ties uniformly at random. We show that $h$-\textsf{Majority} achieves the nearly-optimal trade-off between the sample size and the consensus time, among a broad class of consensus dynamics. In particular, we prove the following results. For every sample size $h \ge 3$ and for every initial configuration, we prove that the process reaches consensus with high probability within $\widetilde{O}\left(1+\min\left\{\frac{1}{\min\{h^2p_{\max},1\}},\frac{\sqrt{n}}{h}\right\}\right)$ rounds, where $n$ is the number of nodes and $p_{\max}$ is the largest initial fraction of nodes supporting any single opinion. This is the first bound on the consensus time for $h$-\textsf{Majority} that holds for every $h\ge3$ and every initial configuration. When the initially most popular opinion has a sufficiently large lead over every other opinion, we show that all nodes adopt this opinion with high probability within $O(\log n/\min\{h^2p_{\max},1\})$ rounds. We establish a matching lower bound up to polylogarithmic factors for any fixed update rule that treats all opinions symmetrically and that selects either a sampled opinion or the node's current opinion.