{"id":"arxiv/2610.40562","url":"https://arxiv.org/abs/2610.40562","tags":["cs.DC","cs.DS","math.PR"],"score":0,"title":"Nearly-Optimal Time-Sample Trade-off in Consensus Dynamics","domain":"cs.DC","source":"arxiv","authors":["Francesco d'Amore","Joel Rybicki","Nobutaka Shimizu","Takeharu Shiraga","Robin Vacus"],"reviews":0,"subject":"cs.DC","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-10-29","reactions":{}}