3-Majority and 2-Choices with Many Opinions

我们首次提出了关于同步共识动态（特别是3-Majority和2-Choices）在任意数量意见下的几乎最优的共识时间界限。在同步共识动态中，我们考虑一个具有自环的完全图，该图有$n$个顶点，每个顶点持有一个来自集合$\{1,\dots,k\}$的意见。在每个离散时间轮次中，所有顶点根据给定的协议同时更新它们的意见。目标是达成一致，即所有顶点支持相同的意见。 在3-Majority中，每个顶点随机选择三个邻居（可以重复），并将其意见更新为多数意见，平局时随机打破。在2-Choices中，每个顶点随机选择两个邻居（可以重复）。如果选定的顶点持有相同的意见，则该顶点采纳该意见；否则，它保留当前的意见直到下一轮。 在此基础上，我们改进了之前一系列的工作[Becchetti等人, SPAA'14]、[Becchetti等人, SODA'16]、[Berenbrink等人, PODC'17]和[Ghaffari和Lengler, PODC'18]，证明了对于每一个$2 \le k \le n$，3-Majority（或2-Choices）分别以高概率在$\widetilde{\Theta}(\min\{k,\sqrt{n}\})$（或$\widetilde{\Theta}(k)$）轮内达成共识。在这项工作之前，3-Majority的最佳已知上界是当$k \ll n^{1/3}$时为$\widetilde{O}(k)$，其他情况下为$\widetilde{O}(n^{2/3})$；而对于2-Choices，当$k \ll \sqrt{n}$时，共识时间为$\widetilde{O}(k)$。

该论文试图解决同步共识动态中的3-Majority和2-Choices协议在任意数量意见下的共识时间问题。具体来说，它旨在确定这些协议达到所有节点持相同意见所需的时间界限。这是一个之前已有研究但未完全解决的问题。

论文的关键思路是提供几乎最优的边界来描述3-Majority和2-Choices协议达成共识所需的轮数。对于3-Majority，证明了共识可以在\(\widetilde{\Theta}(\min\{k,\sqrt{n}\})\)轮内达成；对于2-Choices，则是在\(\widetilde{\Theta}(k)\)轮内达成，这里\(n\)是节点数量，\(k\)是初始不同意见的数量。这比之前的最佳上界有显著改进。

亮点包括：1）提供了更紧致的理论分析，改善了先前关于3-Majority和2-Choices共识时间的理解；2）适用于任意数量的意见，扩展了以往研究的应用范围；3）虽然摘要中没有提到实验设计、数据集或开源代码，但理论上严格的证明为后续实证研究奠定了基础；4）指出了当\(k \le n\)时的具体表现，这是值得进一步研究的方向。

最近的相关研究包括：[Becchetti et al., SPAA'14]、[Becchetti et al., SODA'16]、[Berenbrink et al., PODC'17] 和 [Ghaffari and Lengler, PODC'18]。这些研究都在探索如何更快地实现网络中的一致性，特别是在大规模分布式系统中。