Brief Announcement: What's Live? Understanding Distributed Consensus
Brief Announcement: What's Live? Understanding Distributed Consensus
复制标题
简短公告：有什么直播？
DOI：
10.1145/3465084.3467947
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Liu, Yanhong A.
中科院分区：
文献类型：
--
作者：
Chand, Saksham;Liu, Yanhong A.
Paxos 等分布式共识算法已被广泛研究。许多不同的活性属性和假设已经被描述出来，但是没有系统的比较来更好地理解这些属性。本文系统地研究和比较了 30 多种著名共识算法和变体所描述的不同的活性属性。我们引入了一种精确的高级语言，并在该语言中正式指定了这些属性。然后，我们创建一个活性属性的层次结构，结合所使用的假设的两个层次结构和所做的断言的层次结构，并比较确保这些属性的算法的优点和缺点。我们的正式规范和系统比较导致发现了各种规定的活性特性中的一系列问题。我们还开发了这些活跃属性的 TLA+ 规范，并使用执行步骤的模型检查来说明 Paxos 的活跃模式。
Distributed consensus algorithms such as Paxos have been studied extensively. Many different liveness properties and assumptions have been stated for them, but there are no systematic comparisons for better understanding of these properties.This paper systematically studies and compares different liveness properties stated for over 30 prominent consensus algorithms and variants. We introduced a precise high-level language and formally specified these properties in the language. We then create a hierarchy of liveness properties combining two hierarchies of the assumptions used and a hierarchy of the assertions made, and compare the strengths and weaknesses of algorithms that ensure these properties. Our formal specifications and systematic comparisons led to the discovery of a range of problems in various stated liveness properties. We also developed TLA+ specifications of these liveness properties, and we used model checking of execution steps to illustrate liveness patterns for Paxos.
登录
查看更多内容
DOI：
--
发表时间：
2010
期刊：
影响因子：
--
作者：
D. Malkhi
通讯作者：
D. Malkhi
DOI：
--
发表时间：
2001
期刊：
ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing
影响因子：
--
作者：
James H. Anderson;Yong
通讯作者：
Yong
中等复杂的 Paxos 变得简单：分布式算法的高级可执行规范
DOI：
--
发表时间：
2017
期刊：
ACM-SIGPLAN International Conference on Principles and Practice of Declarative Programming
影响因子：
--
作者：
Yanhong A. Liu;Saksham Chand;S. Stoller
通讯作者：
S. Stoller
衷心感谢以色列理工学院的慷慨财政帮助 致谢
DOI：
--
发表时间：
--
期刊：
影响因子：
--
作者：
D. Malkhi
通讯作者：
D. Malkhi
从总订单到数据库复制
DOI：
--
发表时间：
2002
期刊：
Proceedings 22nd International Conference on Distributed Computing Systems
影响因子：
--
作者：
Y. Amir;C. Tutu
通讯作者：
C. Tutu