Nearly-Optimal Time-Sample Trade-off in Consensus Dynamics
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 ≥ 3 and for every initial configuration, we prove that the process reaches consensus with high probability within Õ(1+min{1/min{h2pmax,1},√n/h}) rounds, where n is the number of nodes and pmax 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≥3 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{h2pmax,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.
Related
- Nearly optimal Kolmogorov widths under holomorphic mappings
- Nearly optimal packings of equally sized rainbow forests
- Nearly Optimal Fixed-Confidence Best-Arm Identification with 1-Bit Feedback
- Clipped or Unclipped? Finite-Sample Trade-offs for Averaged SGD under Heavy-Tailed Noise
- Stable Movement for Nondual Lipschitz Convex Optimization: Efficiency and Nearly Optimal Oracle Rates
BibTeX
@misc{damore2026nearlyoptimal,
title = {{Nearly-Optimal Time-Sample Trade-off in Consensus Dynamics}},
author = {Francesco d'Amore and Joel Rybicki and Nobutaka Shimizu and Takeharu Shiraga and Robin Vacus},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.40562},
eprint = {2610.40562},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.40562},
}
RIS
TY - UNPB
TI - Nearly-Optimal Time-Sample Trade-off in Consensus Dynamics
AU - Francesco d'Amore
AU - Joel Rybicki
AU - Nobutaka Shimizu
AU - Takeharu Shiraga
AU - Robin Vacus
PY - 2026
DA - 2026/10/29
PB - arXiv
DO - 10.48550/arxiv.2610.40562
UR - https://arxiv.org/abs/2610.40562
AB - 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 ≥ 3 and for every initial configuration, we prove that the process reaches consensus with high probability within Õ(1+min{1/min{h^2p_max,1},√n/h}) 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≥3 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.
ER -