作者：Michael J. Fischer , Nancy A. Lynch , Michael S. Paterson 1983
转载请注明译者：phylips@bmy 2011-3-12
出处：http://duanple.blog.163.com/blog/static/70971767201122011858775/
[序：这篇论文虽然只有短短的6页不到，但却包含了一个分布式系统领域最重要的结论。同时因为该结论的重要性和影响力，该论文获得了2001年度的Edsger W. Dijkstra Prize。这个著名的结论被称为FLP结论或者FLP不可能性，”FLP”即该论文的三位作者Fischer Lynch Paterson的首字母。这三位都是分布式领域非常重要的科学家，尤其是Nancy A. Lynch，她的研究成果几乎遍及所有重要的分布式算法。]
摘要：一致性问题是指在多个进程组成的异步系统中，其中的某些进程可能是不可靠的，如何让可靠的进程在一个值上达成一致。我们证明了针对该问题的任何协议都有不可终止的可能性，即使是在只有一个出错进程的情况下。与此不同的是，在同步系统的情况下的拜占庭将军问题却的确存在解。
1. 导引
在远程进程间达成一致是分布式计算领域最重要的问题之一。同时该问题处于很多分布式数据处理算法，分布式文件管理及容错的分布式应用的核心位置。
在分布式数据库系统中，有一个著名的被称为”事务提交”(transaction commit problem)的该类问题。该问题是指：在一个特定事务处理中的所有数据管理进程，需要在是将事务的结果作用于数据库还是放弃上达成一致。放弃事务执行的结果，有时也是必要的，比如某些数据管理器可能因为某些原因无法执行需要的事务处理。无论最终的决定是什么，为了保证数据库的一致性，所有的数据管理器都必须做出相同的决定。
如果进程参与者和网络都是完全可靠的，那么达到提交问题中的这种类型的一致性需求是很简单的。但是，实际系统可能会面对大量的出错可能，比如进程crash，网络分区，消息的丢失重复或者损坏。甚至还可能碰到拜占庭类型的错误，在这种情况下，出错的进程可能不是简单地完全无法工作，而是甚至可能会发送一些恶意的消息。人们通常希望有一个能在各种出错情况下都尽可能可靠的一致性协议。当然实际上任何协议都可能被各种特别频繁或者非常严重的错误所压垮，因此一个好的协议通常是指那些可以容忍那些预见中的错误的协议。
在本论文中，我们揭示出一个令人吃惊的结论：不存在一个完全正确的异步一致性协议，即使是只有一个进程突发性地死掉。在这里我们不考虑拜占庭类型的错误，同时假设消息系统是可靠的---它能够一次性正确的传送所有的消息。然而，即使有这些假设，如果一个进程恰好在一个非常不合适的时间停止运行，也会导致分布式提交协议无法达到一致。因此，如果没有关于计算环境的更进一步的假设或者关于所能容忍的错误类型更多的限制，这个问题根本就没有健壮的解决方案。
我们证明的关键在于处理过程是完全异步的，也就是说，对于进程的处理速率以及消息传输延时没有任何假设。同时我们假设进程无法访问同步时钟，因此就不能使用那些依赖于超时的算法。(尤其是不能使用[DS1]中的解决方案)。最后，我们也没有假定可以检测出死进程，因此对一个进程来说，它无法判断另一个进程是否死掉了还是只是在慢速运行。
我们的不可能性结论可以应用在一个很弱的一致性问题上。假设每个进程从一个{0,1}中的初始值开始；正常的进程最后通过进入一个适当的决议状态在{0,1}中的一个值上达成决议；最终所有达到决议状态的正常进程必须选择相同的值。为了不可能性的证明，我们只要求某个进程最终可以达到决议状态即可{!即我们需要证明没有一个进程最终可以达到一个决议状态，这个结论更具通用性，如果这都不可能，那么要让所有正常进程都达到一个决议状态且还要选择相同的值，就更不可能了}。(当然，任何有用的算法都应当保证所有正常的进程最终会达到决议状态)。该问题其实存在一个平凡解，比如总是让进程选择0，通过规定0和1都必须是针对不同的初始状态下可能的决议值来排除这个解。
我们的系统模型很通用，这样就可以保证我们的不可能性证明也可以有更大的通用性。进程可以用相互之间可以进行通信的自动机(具有无限多个的可能状态)来表示。在每个原子性的步骤里，一个进程可以尝试进行消息接收，根据是否有消息到达来决定如何执行本地计算，向其他进程发送消息。特别地，我们假设进程具有“原子性广播”的能力，即一个进程可以在一个步骤里将相同的消息发送给其他所有进程，同时可以保证如果其中一个正常进程收到了该消息，那么其他所有的正常进程也肯定会收到该消息。只要目标进程不断的尝试接收消息，那么发给它的消息最后都会被收到，只是消息可以被任意地延迟或者乱序传输。
当前所使用的异步提交协议看起来都有其脆弱性---在算法执行的某个时间窗口内，某个进程的延迟或者不可访问性都可能导致整个算法不确定性地等待。这也正说明了它们遵守我们的不可能性结论，而每个提交协议都有这样的一个窗口，这也已逐渐成为大家的共识。
2. 一致性协议
假设一个具有N(N>2)个进程的异步系统的一致性协议P。每个进程p有一个1-bit的输入寄存器xp，一个值域为{b,0,1}的输出寄存器yp，以及一个无限大的内部存储器。输入输出寄存器的值，加上程序计数器pc以及内部存储器共同构成了进程的内部状态。初始状态规定除输入寄存器外其他都具有固定的初始值，尤其是输出寄存器初始值为b。当输出寄存器具有状态0或者1时的，此时的状态被成为决议状态(decision state)。P的状态由一个转换函数来控制。当进程一旦到达决议状态(decision state)后，该转换函数就不能再改变输出寄存器的值，这就意味着输出寄存器实际上只能“write once”。整个系统P是由跟每个进程关联的转换函数及输入寄存器的值来描述的{!因为其他的比如输出寄存器等的初始值都是固定的}。
进程间通过发送消息进行通信。一个消息是一个(p,m)对，p代表目标进程名称，m代表来自一个固定集合M的消息值。消息系统维护了一个被称为消息缓冲区的多值集合(multiset)，这里面保存了那些被发送但是还没有被传送的消息。它支持两种类型操作：
Send(p,m):将消息(p,m)放入消息缓冲区
Receive(p):从消息缓冲区中删除某条消息(p,m)，然后返回m，这时我们称消息(p,n)被传送(delivered)；或者返回一个特殊的标志Φ，同时缓冲区保持原样。
因此，实际上消息系统的运行是非确定性的。仅满足一个条件：如果receive(p)被无限次的调用，那么消息缓冲区的所有(p,m)消息最后都会被发送。特别地，消息系统允许针对receive(p)返回有限次的Φ，即使目前消息缓冲区已经存在消息(p,m)。
系统的一个configuration由每个进程的内部状态以及消息缓冲区的内容组成。一个initial configuration是指所有进程都处在初始状态同时消息缓冲区为空的那些configuration。
一个step使一个configuration转变为另一个configuration，而它则是由一个进程p本身执行的一些基本步组成。令C代表一个configuration，这些基本步可以分为两个阶段，首先receive(p)会作用在C的消息缓冲区上获取一个值m，m属于M∪Φ。之后，根据p在C中的内部状态以及m的值，p进入一个新的内部状态，然后给其他进程发送有限数量的消息。因此进程的执行是确定性的，而一个step是由一个e=(p,m)对完全确定的，我们称之为一个事件(更准确的说该事件应该是指进程p收到了消息m{!有时虽然进程执行了receive(p)，但它可能收到的是Φ，此时的事件应该是(p, Φ)。也就是说到底是何事件应该等进程收到该step的消息后才能确定，同时也就是说事件(p, m)是指进程p确实收到了消息m，而不仅仅是执行了一次receive(p)。})。e(C)则代表该事件执行之后的configuration，同时我们称e是可应用于(applied to) C的。同时可以看出事件(p, Φ)可以一直应用在C上，因此进程总是可以有一个step可以选择，不会无路可走。
一个从C开始的schedule是一系列从C开始的逐次可应用的事件组成的有限或者无限序列б。一系列相关联step的序列称为run。如果б是有限集，我们令б(C)代表结果configuration，那么我们称该configuration是从C可达的(reachable)。 那些从某些初始configuration可达的configuration称之为可访问的(accessible)。我们下面提到的configuration都是可访问的。
下面的定理表明了schedule具有交换性。
Lemma 1.假设从某个configuration开始的scheduleб1和б2，分别可以到达 configuration C1和C2。如果б1和б2里执行各step的进程集合是不相交的，那么б2可以应用于C1，而б1可以应用于C2，同时最后他们将到达相同的configuration C3。如图1.
证明：该结论可以从系统定义中立即得到因为б1和б2没有交集。
如果一个configuration C的某个进程p处于决议状态同时yp=v，我们称该configuration具有决议值v。一个一致性协议如果满足如下两个条件，我们就称之为是部分正确(partially correct)的：
1. 不存在任何一个可访问的configuration具有超过一个的决议值。
2. 对于集合{0,1}中每个值v，总存在某些可访问的configuration具有决议值v。
进程p如果可以执行无限多的step我们就称之为是正常的(nonfaulty)，否则就是出错的。如果在一次运行中最多有一个进程出错，同时发送给正常进程的所有消息最后都能被收到，我们就称此次运行是合法的，。
如果一次运行中，某个进程可以达到决议状态，我们就称此次运行是一次deciding run。如果一个一致性协议在即使存在一个出错进程的情况下依然是partially correct的，同时每次合法的运行都是deciding run，我们就称之为是完全正确(totally correct)的。
3. 主要结论
Theorem Ⅰ.在有一个进程出错的情况下，不存在一个完全正确的一致性协议。
证明.假设它的反面成立，即存在这样的一个完全正确的一致性协议P。然后我们通过证明一系列的定理，而它们最终会导致一个矛盾来完成证明。
基本的思路是指出协议存在会处于永远无法决议状态的可能情形。主要分为两个步骤：第一步，说明存在某个初始configuration，在这个configuration里，决议不可能是预先确定的。第二步，构造出一种合法的运行，该运行可以保证系统永远都无法进入一个决议状态。
令C代表一个configuration，V代表那些从C可到达的configuration的决议值。如果|V|=2，称C是bivalent的。如果|V|=1，称C是univalent的，同时根据相应的决议值，称之为是0-valent或者1-valent的。根据P的完全正确性，可知所有合法的运行的V都不等于Φ。
Lemma 2. P具有一个bivalent的初始configuration。
证明:假设该定理不成立。那么根据假设P满足partially correct，得出P肯定同时存在0-valent和1-valent的初始configuration。如果两个初始configuration仅仅是在一个进程的xp值上不同我们就称之为相邻{!因为它们都是初始configuration，所以它们不同的只是xp的值}。这样，任意两个初始configuration都可以通过一个由初始configuration组成的链(链中的configuration都是相邻的)连接起来。因此，肯定存在一个0-valent的初始configuration C0与一个1-valent的初始configuration C1相邻{!因为所有的初始configuration都是相连的，而这些初始configuration除了0-valent就是1-valent的，因此肯定有个地方将0-valent和1-valent的连接起来，否则它们就是两个不连通的子集}。假设p就是这两个相邻的初始configuration所不同的那个进程。
现在考虑一个从C0开始的某个合法的deciding run，在该次运行中，进程p不与任何step相关，令б代表其相关的schedule。那么б也可以应用于C1，而且在这两次运行中，相应的configuration唯一的区别就在于进程p的内部状态。可以很容易的说明，这两次运行最终应该到达相同的决议值{!根据假设P是完全正确的，它可以容忍一个进程出错，那么我们就假设进程p出错了，它无法接受消息也无法发送消息，这样对于C0，C1来说，进程p就不会对运行产生任何影响，因此它们应该到达相同的决议值}。如果决议值为1，那么C0就是bivalent的，否则C1就是bivalent的。无论是哪种情况，都与我们的假设“不存在一个bivalent的初始configuration”相矛盾。证明完毕。
Lemma 3.令C是P的一个bivalent的初始configuration，同时令e=(p,m)是一个可以应用于C的事件。令?代表所有从C开始的没有应用事件e的configuration的集合，令?=e(?)={e(E)|E属于?，同时e可以应用于E}{!注意对于?来说，e是它应用的最后一个事件，也就是说?就是对?中所有元素应用一个e之后得到的新集合}。那么?也包含一个bivalent的configuration。
证明：因为e是可以应用于C的，那么根据?的定义及消息传输可以被任意延迟的事实，可以得出e可以被应用于?中的每个E。
现在假设?不包含任何bivalent的configuration，这样每个属于?的configuration D都是univalent的。下面，我们继续进行以导出一个矛盾来。
令Ei代表一个可以从C到达的i-valent configuration，i=0,1。(Ei肯定存在，因为C是bivalent的) {?也有可能C可到达的都是bivalent的而没有univalent的，又如何保证存在这样的E0和E1呢。因为C是bivalent的，那么肯定存在一些yp=0和yp=1的configurations，对于这些configurations 因为它们的yp不能在改变，因此它们肯定是univalent的}。如Ei属于?，令Fi=e(Ei)属于?。否则，e肯定在到达Ei过程中被应用了，因此存在一个属于? 的Fi，Ei是从该Fi可到达的。在这两种情况中，根据假设Fi不是bivalent的，所以Fi肯定都是i-valent的，只是一种情况是Ei从Fi可达，另一种情况则是Fi从Ei可达，如下图所示。因为Fi属于?，i=0,1，因此?肯定同时包含0-valent和1-valent的configurations。
对于两个configurations来说，如果一个是另一个执行一个单一的step后的结果，那么我们就称它们是邻居。通过一个简单的归纳{?这个简单的归纳具体是如何的呢？实际上可以这样来理解，首先?中的元素不是0-valent就是1-valent的，而?中的元素又都来源于?，也就是说?中的元素都是通过一条e边与?中元素相连，两个集合中的元素是一一对应的，这样我们可以根据?中元素到底与?中的0-valent的还是1-valent的相连，而把?分为两类?0和?1，同时我们又知道?中的元素又都是从C可到达的。也就是说?中的任意元素都是通过一些有向边连通起来的(准确的说应该是有这个性质：即把有向边都看成无向边，?肯定是连通的)，这样肯定存在一条?0到?1的边，即下面的e’，实际上我们不确定e’是导致C0->C1,还是C1->C0，但是这都不影响证明，下面只是选择了C0->C1，换成C1->C0结果也是一样。}，可以得出?中存在一个邻居C0，C1{!?所以此处的C0，C1并不是0-valent和1-valent，因为它们是邻居，它们应该就是两个configurations，而且至少C0应该是bivalent的。所以应该理解为Ci中的i就是代表与Di相连接。}，满足Di=e(Ci)是i-valent的，i=0,1。为了不失掉一般性，令C1=e’(C)，e’=(p’,m’)。
CASE1：如果p1不等于p，那么根据Lemma 1，D1=e’(D0)。这是不可能的，因为一个0-valent任何后继configuration肯定都是一个0-valen的。参见图2
CASE2：如果p’=p，那么考虑从C0开始的一个p无关的deciding run，其相关schedule为 б，令A=б(C0)。根据Lemma 1，б可以应用于Di，而且它可以导致一个i-valent的configuration Ei=б(Di)，i=0,1。同时根据Lemma 1，e(A)=E0 而e(e’(A))=E1。参见图3.
因此A是bivalent的，这是不可能的，因为A是univalent的{!因为A是一个C0开始的一个p无关的deciding run，根据deciding run的定义，此时A已有进程处于决议状态，所以A肯定是univalent的}{?问题是如何确保这样的一个p无关的deciding run的存在性}。
在所有情况下，我们都得出了一个矛盾，因此?肯定存在一个bivalent的的configuration。
任何从一个brivalent的初始configuration开始到达一个univalent的configuration的deciding run，肯定存在某一个step是从一个bivalent的configuration到达一个univalent的configuration，这样的一个步骤就决定了最终的决议值。我们现在来证明，总是有可能让系统以避免选择这样的步骤的方式，这样就能形成一个合法的non-deciding run。
该non-deciding run从一个初始configuration开始，分多个阶段组成。首先通过如下的方式，我们来保证它是合法的。维护一个进程队列，它们初始的顺序任意，在configuration里的消息缓冲区的消息按照发送时间排序，发送的早的排在前面。每个阶段由一个或者多个step组成。在每个阶段中，如果开始时进程队列中的第一个进程的消息队列不为空，那么需要等到该进程在该阶段中执行了一个step，收到它最早的一条消息后，该阶段才算结束。之后，该进程被移到进程队列的尾部。因此，在无限多的阶段序列中，可以保证每个进程都可以执行无限多的step，收到所有发给它的消息。因此，该run就是合法的。下面的问题就是需要说明，按照上面的方式如何避免一个决议的产生。
令C0代表一个bivalent的初始configuration，根据Lemma 2肯定存在这样的一个configuration。从C0开始执行，同时我们要保证后面的每个阶段都是从一个bivalent的configuration开始。假设configuration C是bivalent的，同时此时处在队列头的进程是p。令m是C的消息缓冲区中最早传送给p的消息，如果消息缓冲区中没有给p的消息，m就是Φ。令e=(p,m)。根据Lemma 3.存在一个bivalent的configuration C’， 通过一个e作为最后被应用事件的schedule，它是从C可达的。该schedule对应的那些step序列，就构成了该阶段的那些step。
因此每个阶段都以一个bivalent的configuration结束，这样就可以成功构建出一个无限的schedule的各个阶段。该run的运行是合法的，但是永远都无法达到一个决议状态。
由此证明了P不是完全正确的。
4. 初始死进程
在这一节，我们提出一个解决如下情况下的一致性问题的协议：总共有N个进程，其中半数以上的是正常进程，在协议执行过程中没有进程会死掉，但是进程不知道初始时到底是哪些进程死掉了。
该协议分为两个步骤。第一个步骤，进程首先构建一个有向图G，每个进程由图中的一个节点表示。每个进程将它自己的进程号广播给其他进程，之后会监听来自其他L-1个进程的消息，L=ceil((N+1)/2)。如果j收到了一条来自i的消息，那么就向图G中加入一条i->j的边。因此，G中节点的入度为L-1。
第二个步骤，进程构建图G+，即图G的传递闭包{!有向图G的传递闭包定义为：G*=(V,E*),其中E*={(i,j)}:图G中存在一条从i到j的路径。}。在该阶段完成时，除了那些原本就与k相关联的边，每个进程k将能够获知图G+中所有与k相关的边(j,k)。
为了完成该步骤。每个进程会向其他所有进程广播自己的进程号初始值及它在第一个步骤里得到的L-1个进程名称。之后，它就会等待在阶段1中获知的那些向它发送消息的进程发送的阶段2消息{!即那些进程的进程号初始值及它们在第一个步骤里得到的L-1个进程名称}。最初，进程们只知道那些在阶段中向它发送消息的L-1个进程，但是通过它在阶段2中收到的消息它就能知道其他的祖先节点。进程会一直等待，直到收到那些它已知道的进程的消息为止{!比如它一开始知道P-1个进程，那么它需要等待着P-1个进程的消息，当其中的一个进程假设为i发送消息过来后，i会把它自己的祖先告知等待进程，假设i的祖先中有一个新的进程j，那么此时等待进程就又知道了j，那么它就需要继续等待进程j的消息。也就是这样的一个过程中需等待的节点是逐步更新的，最终它就能知道它所有的祖先}。
这样，每个进程最后就能获知图G中它的自己的祖先，以及所有与这些祖先相关联的边，因此它就可以计算出图G+中的所有与它的祖先相关联的边。这就使得它可以判定它的哪些祖先属于G+的一个初始闭包，即一个没有入边的闭包{!即在闭包外的节点肯定不存在一条指向闭包内的节点的边，如果存在这样的一个节点，那说明它是闭包内的一节点k的祖先，但是根据后面，我们可以知道k也应该是它的祖先，那么它应该在闭包内。}，对于节点k来说，如果它本身又是它所有祖先的祖先，那么我们就认为节点k属于一个初始闭包{!可以看出一个初始闭包，实际上就是有向图中的一个全连通子集}。因为G+的每个节点至少有L-1个祖先，因此只能存在一个初始闭包，同时它至少有L个节点{!因为为了保证没有入边，它必须要将指向它的节点的至少L-1个祖先全部包含在内，因此它至少有L个节点。？但是有一个问题如何确保这个初始闭包集合不是空的呢？}，这样在第二个步骤完成后，每个进程就都知道组成该闭包的所有进程集合了{!下面看进程k如何是如何知道的？每个节点又有至少L-1个祖先，加上它自己就是L个节点，而闭包也是至少有L个节点，又L= ceil((N+1)/2,可知初始闭包中的节点肯定与k及其祖先有交集，根据初始闭包的性质，可知初始闭包中的节点肯定是k的祖先，因此进程k通过判断它的哪些祖先属于初始闭包就可以得知闭包中都是哪些进程}。
最后，每个进程使用一个确定性的规则，在初始闭包中的进程的初始值上做出一个决议。因为所有的进程都知道初始闭包中所有成员的初始值，因此它们最后会得到相同的决议值。
该协议的正确性证明了如下定理：
Theorem .如果在运行过程中没有进程死掉，同时有半数以上的进程是正常的，那么存在一个partially corrent的一致性协议，可以保证所有正常的进程可以达成一个决议。
致谢…
评论