Improved communication complexity of fault-tolerant consensus
Improved communication complexity of fault-tolerant consensus
复制标题
提高容错共识的通信复杂度
DOI：
10.1145/3519935.3520078
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Olkowski, Jan
中科院分区：
文献类型：
--
作者：
Hajiaghayi, Mohammad T.;Kowalski, Dariusz R.;Olkowski, Jan
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 [PODC 1998] and Aspnes and Waarts [SICOMP 1996, JACM 1998] 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 Θ(n3/2/√logn) 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 amortizedO(1) communication bits per process. We design an algorithm against adaptive adversary that reduces the communication gap by nearly linear factor toO(√n·n) bits per process, while keeping almost-optimal (up to factorO(log3n)) time complexityO(√n·log5/2n).More surprisingly, we show this complexity indeed can be lowered further, but at the expense of increasing time complexity, i.e., there is atrade-offbetween communication complexity and time complexity. More specifically, our main Consensus algorithm allows to reduce communication complexity per process to any value fromntoO(√n·n), as long as Time × Communication =O(n·n). Similarly, reducing time complexity requires more random bits per process, i.e., Time × Randomness =O(n·n).Our parameterized consensus solutions are based on a few newly developed paradigms and algorithms for crash-resilient computing, interesting on their own. The first one, called aFuzzy Counting, provides for each process a number which is in-between the numbers of alive processes at the end and in the beginning of the counting. Our deterministic Fuzzy Counting algorithm works inO(log3n) rounds and uses onlyO(n) amortized communication bits per process, unlike previous solutions to counting that required Ω(n) bits. This improvement is possible due to a newFault-tolerant Gossipsolution withO(log3n) rounds using onlyO(||·n) communication bits per process, where || is the length of the rumor binary representation. It exploits distributed fault-tolerant divide-and-conquer idea, in which processes run aBipartite Gossipalgorithm for a considered partition of processes. To avoid passing many long messages, processes use a family of small-degree compact expanders forlocal signalingto their overlay neighbors if they are in a compact (large and well-connected) party, and switch to a denser overlay graph whenever local signalling in the current one is failed.
登录
查看更多内容
现实故障模型中的简单恒定时间共识协议
DOI：
10.1145/65950.65956
发表时间：
1989
期刊：
J. ACM
影响因子：
--
作者：
B. Chor;Michael Merritt;D. Shmoys
通讯作者：
D. Shmoys
影响因子：
3.1
作者：
D. Kowalski;Jaroslaw Mirek
通讯作者：
Jaroslaw Mirek
影响因子：
9.8
作者：
Dan Alistarh;Seth Gilbert;R. Guerraoui;Morteza Zadimoghaddam
通讯作者：
Morteza Zadimoghaddam
与拜占庭节点的网络中的快速协议
影响因子：
1.9
作者：
Bogdan S. Chlebus;D. Kowalski;J. Olkowski
通讯作者：
J. Olkowski
每个处理器预期 O(n log² n) 操作的随机共识
DOI：
10.1137/s0097539792240881
发表时间：
1996
期刊：
SIAM J. Comput.
影响因子：
--
作者：
J. Aspnes;Orli Waarts
通讯作者：
Orli Waarts