论文标题
提高了易于故障共识的沟通复杂性
Improved Communication Complexity of Fault-Tolerant Consensus
论文作者
论文摘要
共识是分布式计算中最彻底研究的问题之一，但数十年来仍然没有桥接的复杂性差距。特别是，自Bar-Joseph and Ben-Or [1998] \ cite {Bar-Josephb98}以及Aspnes and Waarts [1996，1996，1998]与（强）自适应对手崩溃过程任意在线的快速随机共识的复杂性。通信位数上最著名的上限是$θ（\ frac {n^{3/2}}} {\ sqrt {\ log {n}}}）$每个进程，而最佳下限为$ω（1）$。这与（弱）遗忘对手的随机共识形成鲜明对比，为此，几乎最佳的算法保证摊销$ o（1）$ communication bits process \ cite \ cite \ cite {gk-sode-10}。我们设计了针对自适应对手的算法，将通信差距降低到$ o（\ sqrt {n} \ cdot \ cdot \ text {polylog} n）$ bits $ bits $ bits $ bits $ bits $ bits $（\ log^3 n）$ o（\ log^3 n）$ o（\ log^3 n）$ o（\ log^3 n）$（\ log^3 n）$（\ log^3 n） $ O（\ sqrt {n} \ cdot \ log^{5/2} n）$。 更令人惊讶的是，我们表明确实可以进一步降低这种复杂性，但以增加时间复杂性为代价，即交流复杂性和时间复杂性之间存在一个{\ em折衷}。更具体地说，我们的主要共识算法允许每个过程的通信复杂性从$ \ text {polylog} n $到$ o（\ sqrt {n} \ cdot \ cdot \ text {polylog} n）$，只要时间$ \ times $ \ times $ \ times $ communication $ = o（n \ cdot \ cdot \ cdot \ cdot \ cdot \ polylyg} n n n n n n n n \ polylog ogylog，同样，缩短时间复杂性需要每个过程的随机位，即时间$ \ times $ anturalness $ = o（n \ cdot \ text \ text {polylog} n）$。
Consensus is one of the most thoroughly studied problems in distributed computing, yet there are still complexity gaps that have not been bridged for decades. In particular, in the classical message-passing setting with processes' crashes, since the seminal works of Bar-Joseph and Ben-Or [1998] \cite{Bar-JosephB98} and Aspnes and Waarts [1996, 1998] \cite{AspnesW-SICOMP-96,Aspnes-JACM-98} in the previous century, there is still a fundamental unresolved question about communication complexity of fast randomized Consensus against a (strong) adaptive adversary crashing processes arbitrarily online. The best known upper bound on the number of communication bits is $Θ(\frac{n^{3/2}}{\sqrt{\log{n}}})$ per process, while the best lower bound is $Ω(1)$. This is in contrast to randomized Consensus against a (weak) oblivious adversary, for which time-almost-optimal algorithms guarantee amortized $O(1)$ communication bits per process \cite{GK-SODA-10}. We design an algorithm against adaptive adversary that reduces the communication gap by nearly linear factor to $O(\sqrt{n}\cdot\text{polylog } n)$ bits per process, while keeping almost-optimal (up to factor $O(\log^3 n)$) time complexity $O(\sqrt{n}\cdot\log^{5/2} n)$. More surprisingly, we show this complexity indeed can be lowered further, but at the expense of increasing time complexity, i.e., there is a {\em trade-off} between communication complexity and time complexity. More specifically, our main Consensus algorithm allows to reduce communication complexity per process to any value from $\text{polylog } n$ to $O(\sqrt{n}\cdot\text{polylog } n)$, as long as Time $\times$ Communication $= O(n\cdot \text{polylog } n)$. Similarly, reducing time complexity requires more random bits per process, i.e., Time $\times$ Randomness $=O(n\cdot \text{polylog } n)$.
