betaFeedback

WorksComputer Science

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 hh-Majority, in which every node independently samples hh nodes uniformly at random with replacement in each round and adopts a most frequent sampled opinion, breaking ties uniformly at random. We show that hh-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≥3h \ge 3 and for every initial configuration, we prove that the process reaches consensus with high probability within O~(1+min⁡{1min⁡{h2pmax⁡,1},nh})\widetilde{O}\left(1+\min\left\{\frac{1}{\min\{h^2p_{\max},1\}},\frac{\sqrt{n}}{h}\right\}\right) rounds, where nn is the number of nodes and pmax⁡p_{\max} is the largest initial fraction of nodes supporting any single opinion. This is the first bound on the consensus time for hh-Majority that holds for every h≥3h\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⁡{h2pmax⁡,1})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.

Paper details

vlnc:W_ecgp9sru
Version
v2 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 11

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…