Nearly-Optimal Time-Sample Trade-off in Consensus Dynamics

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.