Brief Announcement: Deterministic Consensus and Checkpointing with Crashes: Time and Communication Efficiency
Brief Announcement: Deterministic Consensus and Checkpointing with Crashes: Time and Communication Efficiency
复制标题
简短公告：确定性共识和崩溃检查点：时间和通信效率
DOI：
10.1145/3519270.3538471
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Olkowski, Jan
中科院分区：
文献类型：
--
作者：
Chlebus, Bogdan S.;Kowalski, Dariusz R.;Olkowski, Jan
我们研究了同步分布式系统中的共识和检查点。有n个节点通过发送消息进行通信，任何两个节点都可以直接通信。节点容易崩溃，崩溃次数的上限为t。算法使用选择的覆盖网络来节省通信量。我们探索使用Ramanujan图作为这样的覆盖网络。我们证明了Ramanujan图的拓扑特性有利于分布式算法的容错性和时间/通信效率。我们的共识算法假设二进制输入值，运行时间为O（t），发送O（n+t log t）位。该算法发送的最佳数量为O（n）的位为t=O（n/log n），因此，对于这个范围的t它改进了算法的Galil，迈耶和杨[FOCS 1995]，也发送O（n）位，但在指数时间工作。共识算法可以被实现为使得节点在一轮中向至多一个节点发送消息，同时保持渐近时间和通信性能界限。我们的检查点算法运行在线性时间O（n）和O（n log 7 n）消息。它改进了Galil，Mayer和Yung [FOCS 1995]的最有效的通信和时间最优算法，对于任何选择的常数ε>0，该算法可以发送O（n1+ε）消息。
We study consensus and checkpointing in synchronous distributed systems. There are n nodes that communicate by sending messages, and any two nodes can communicate directly. The nodes are prone to crashing, with an upper bound t on the number of crashes. Algorithms use overlay networks of choice to save on the amount of communication. We explore using Ramanujan graphs as such overlay networks. We demonstrate that Ramanujan graphs have topological properties conducive to fault-tolerance and time/communication efficiency of distributed algorithms. Our consensus algorithm assumes binary input values, runs in O(t) time and sends O(n+t log t) bits. The algorithm sends the optimum number O(n) of bits for t=O(n/log n), thus for this range of t it improves on the algorithm by Galil, Mayer and Yung [FOCS 1995] that also sends O(n) bits but works in exponential time. The consensus algorithm can be implemented such that a node sends a message to at most one node at a round while maintaining the asymptotic time and communication performance bounds. Our checkpointing algorithm runs in linear time O(n) and with O(n log7 n) messages. It improves on the most communication-efficient and time-optimal algorithm by Galil, Mayer and Yung [FOCS 1995], which may have O(n1+ε) messages sent, for any chosen constant ε>0.
登录
查看更多内容
现实故障模型中的简单恒定时间共识协议
DOI：
10.1145/65950.65956
发表时间：
1989
期刊：
J. ACM
影响因子：
--
作者：
B. Chor;Michael Merritt;D. Shmoys
通讯作者：
D. Shmoys
影响因子：
3.1
作者：
D. Kowalski;Jaroslaw Mirek
通讯作者：
Jaroslaw Mirek
换档：动态改变算法以加快达成拜占庭协议
影响因子：
2.5
作者：
A. Bar;Danny Dolev;C. Dwork;H. Strong
通讯作者：
H. Strong
具有最佳通信复杂度的分布式协议
DOI：
--
发表时间：
2010
期刊：
ACM-SIAM Symposium on Discrete Algorithms
影响因子：
--
作者：
Seth Gilbert;D. Kowalski
通讯作者：
D. Kowalski
分布式共识中的最优提前停止（扩展摘要）
影响因子：
3.1
作者：
P. Berman;J. Garay;K. Perry
通讯作者：
K. Perry