Generalized lattice agreement
Generalized lattice agreement
复制标题
广义格协议
DOI：
10.1145/2332432.2332458
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
K. Vaswani
中科院分区：
文献类型：
--
作者：
Jose M. Faleiro;S. Rajamani;K. Rajan;G. Ramalingam;K. Vaswani
晶格协议是分布式系统中的关键决策问题。在此问题中，过程从晶格的输入值开始，必须学习形成链的（非平凡的）值。与共识不同，即使存在单个过程失败也是不可能的，在存在故障的情况下，晶格一致性已被证明是可决定的。在本文中，我们考虑了异步传递系统中的晶格协议问题。我们提出了晶格协议问题的算法，只要大多数流程都是不易用的。该算法具有O（n）消息延迟的时间复杂性，其中n是过程的数量。然后，我们引入了广义晶格协议问题，每个过程都会从无限晶格中接收（潜在无限）的值序列，并且必须学习一个增加值的序列，以使所有学习序列的结合都是一个链，最终每个提出的值都是一个链学会了。我们提出了一种无需等待算法，用于解决广义晶格协议。该算法保证在O（n）消息延迟中学习了正确过程中收到的每个值。我们表明，该算法可用于实现一类复制的状态计算机，可以将（a）命令分类为读取和更新，以及（b）所有更新命令通勤。该算法可用于实现常用数据类型的可序列化且可线化的复制版本。
Lattice agreement is a key decision problem in distributed systems. In this problem, processes start with input values from a lattice, and must learn (non-trivial) values that form a chain. Unlike consensus, which is impossible in the presence of even a single process failure, lattice agreement has been shown to be decidable in the presence of failures. In this paper, we consider lattice agreement problems in asynchronous, message passing systems. We present an algorithm for the lattice agreement problem that guarantees liveness as long as a majority of the processes are non-faulty. The algorithm has a time complexity of O(N) message delays, where N is the number of processes. We then introduce the generalized lattice agreement problem, where each process receives a (potentially unbounded) sequence of values from an infinite lattice and must learn a sequence of increasing values such that the union of all learnt sequences is a chain and every proposed value is eventually learnt. We present a wait-free algorithm for solving generalized lattice agreement. The algorithm guarantees that every value received by a correct process is learnt in O(N) message delays. We show that this algorithm can be used to implement a class of replicated state machines where (a) commands can be classified as reads and updates, and (b) all update commands commute. This algorithm can be used to realize serializable and linearizable replicated versions of commonly used data types.