Comparing the Atomic Commitment and Consensus Problems
Comparing the Atomic Commitment and Consensus Problems
复制标题
原子承诺和共识问题的比较
DOI：
10.1007/3-540-37795-6_7
复制
发表时间：
2003
影响因子：
1
通讯作者：
Bernadette Charron
中科院分区：
文献类型：
--
作者：
Bernadette Charron
我们考虑消息传递系统中的一致性问题，其中进程可能崩溃：每个进程都有一个输入，每个正确的进程必须决定一个输出，使得所有正确的进程决定相同的输出，而这个输出是其中一个进程的输入。共识是容错系统的重要组成部分。众所周知，在异步模型中，即使只有一个进程崩溃，共识也是不可解的[7.13]。然而，真正的系统并不是完全异步的。一些部分同步模型[7.12]，[7.10]中一致可解的部分同步模型更好地逼近真实系统。我们考虑定义如下的部分同步模型[7.12]1：(1)进程具有有界的漂移时钟；(2)存在已知的处理时间和消息延迟的界；(3)不到一半的进程可能崩溃。此外，该模型允许系统不稳定，其中(2)中的界不是在无界的而是有限的周期内保持的，但它最终必须进入一个稳定的界保持的周期。部分同步模型的一致算法永远不会违反安全性，并保证系统一旦变得稳定就具有活性。这个模型的算法在[7.16]中被称为放纵。关于部分同步模型中共识算法的运行时间，我们能说些什么呢？不幸的是，即使在没有失败的情况下，该模型中的任何共识算法都必然具有无限的运行时间，直到[7.13]。
We consider the consensus problem in a message-passing system where processes can crash: Each process has an input, and each correct process must decide on an output, such that all correct processes decide on the same output, and this output is the input of one of the processes. Consensus is an important building block for fault-tolerant systems. It is well-known that consensus is not solvable in an asynchronous model even if only one process can crash [7.13]. However, real systems are not completely asynchronous. Some partially synchronous models [7.12], [7.10] where consensus is solvable better approximate real systems.We consider a partial synchronymodel defined as follows [7.12]1: (1) processes have bounded drift clocks; (2) there are known bounds on processing times and message delays; and (3) less than half of the processes can crash. In addition, this model allows the system to be unstable, where the bounds in (2) do not hold for an unbounded but finite period, but it must eventually enter a stableperiod where the bounds do hold.A consensus algorithm for the partial synchrony model never violates safety, and guarantees liveness once the system becomes stable. Algorithms for this model are called indulgent in [7.16]. What can we say about the running time of consensus algorithms in a partial synchrony model? Unfortunately, even in the absence of failures, any consensus algorithm in this model is bound to have unbounded running times, by [7.13].