我们首次提出了关于同步共识动态(特别是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)$。