betaFeedback

Reading v1View latest version

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-\textsf{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-\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≥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-\textsf{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
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…