摘要：實際上，它也算是最淺顯易見的分布式算法之一了。一個分布式算法，有兩個重要的屬性和，簡單來說是指那些需要保證永遠都不會發(fā)生的事情是指那些最終一定會發(fā)生的事情在這個一致性算法中，有三個參與角色，我們分別用，和來表示。

用于實現(xiàn)高容錯性分布式系統(tǒng)的Paxos算法，一直以來總是被認為是難以理解的，或許是因為對很多人來說，初始版本就像是”希臘語"一樣（最初的論文是以希臘故事展開的形式）[5]。實際上，它也算是最淺顯易見的分布式算法之一了。它的核心就是一個一致性算法——論文[5]中的“synod”算法。在下一個章節(jié)可以看到，它基本上是根據(jù)一個一致性算法所必需滿足的條件自然而然地推斷出來的。最后一個章節(jié)，我們通過將Paxos算法作為構(gòu)建一個實現(xiàn)了狀態(tài)機的分布式系統(tǒng)的一致性實現(xiàn)，來完整地描述它。這種使用狀態(tài)機方法的論文[4]應(yīng)該早已廣為人知，因為它可能已經(jīng)是分布式系統(tǒng)理論研究領(lǐng)域被引用最廣泛的了。

假設(shè)有一組可以提出提案的進程集合。一個一致性算法需要保證：
在這些被提出的提案中，只有一個會被選定。
如果沒有提案被提出，則不會有被選定的提案。
當一個提案被選定后，進程應(yīng)該能獲取被選定提案的信息。

對于一致來說，安全性（Safety）需求是這樣的：
只有被提出的提案才能被選定。
只能有一個值被選中（chosen），同時
進程不能認為某個提案被選定，除非它真的是被選定的那個。

我們不會嘗試去精確地描述活性（Liveness）需求。但是從總體上看，最終的目標是保證有一個提案被選定，并且當提案被選定后，進程最終也能獲取到被選定提案的信息。
一個分布式算法，有兩個重要的屬性：Safety和Liveness，簡單來說：
Safety是指那些需要保證永遠都不會發(fā)生的事情
Liveness是指那些最終一定會發(fā)生的事情

在這個一致性算法中，有三個參與角色，我們分別用Proposer，Acceptor和Learner來表示。在具體實現(xiàn)中，一個進程可能充當不止一種角色，但是在這里我們并不關(guān)心它們之間的映射關(guān)系。

假設(shè)不同的參與者之間可以通過發(fā)消息來進行通信，我們使用普通的非拜占庭模式的異步模型：
每個參與者以任意的速度運行，可能會因停止而執(zhí)行失敗，也可能會重啟。當一個提案被選定后，所有的參與者都有可能失敗然后重啟，除非這些參與者可以記錄某些信息，否則是不可能存在一個解法的。
消息在傳輸中可能花費任意時間，可能會重復，也可能丟失，但不會被損壞（不會被篡改，即不會發(fā)生拜占庭問題）。

選定提案最簡單的方式就是只有一個Acceptor存在。Proposer發(fā)送提案給Acceptor，Acceptor會選擇它接收到的第一個提案作為被選提案。雖然簡單，這個解決方案卻很難讓人滿意，因為當Acceptor出錯時，整個系統(tǒng)就無法工作了。

因此，我們應(yīng)該選擇其他方式來選定提案，比如可以用多個Acceptor來避免一個Acceptor的單點問題。這樣的話，Proposer向一個Acceptor集合發(fā)送提案，某個Acceptor可能會通過（accept）這個提案。當有足夠多的Acceptor通過它時，我們就認為這個提案被選定了。那么怎樣才算是足夠多呢？為了確保只一個提案被選定，我們可以讓這個集合大到包含了Acceptor集合中的多數(shù)成員。因為任意兩個多數(shù)集（majority）至少包含一個公共成員，如果我們再規(guī)定一個Acceptor只能通過一個提案，那么就能保證只有一個提案被選定（這是很多論文都研究過的多數(shù)集的一個普通應(yīng)用[3]）。

假設(shè)沒有失敗和消息丟失的情況，如果我們希望在每個Proposer只能提出一個提案的前提下仍然可以選出一個提案來，這就意味著如下需求：

P1. 一個Acceptor必須通過它收到的第一個提案。

但是這個需求會引發(fā)另外的問題。如果有多個提案被不同的Proposer同時提出，這會導致雖然每個Acceptor都通過了一個提案，但是沒有一個提案是由多數(shù)人通過的。甚至即使只有兩個提案被提出，如果每個都被差不多一半的Acceptor通過了，哪怕只有一個Acceptor出錯都可能導致無法確定該選定哪個提案。
比如有5個Acceptor，其中2個通過了提案a，另外3個通過了提案b，此時如果通過提案b的3個當中有一個出錯了，那么a和b的通過數(shù)都為2, 這樣就無法確定了。

P1再加一個提案被選定需要由半數(shù)以上Acceptor通過的這個需求，暗示著一個Acceptor必須要能通過不止一個提案。我們?yōu)槊總€提案分配一個編號來記錄一個Acceptor通過的那些提案，于是一個提案就包含一個提案編號以及它的value值。為了避免造成混淆，需要保證不同的提案具有不同編號。如何實現(xiàn)這個功能依賴于具體的實現(xiàn)細節(jié)，在這里我們假設(shè)已經(jīng)實現(xiàn)了這種保證。當一個具有value值的提案被多數(shù)Acceptor通過后，我們就認為該value被選定了。同時我們也認為該提案被選定了。

我們允許多個提案被選定，但是我們必須保證所有被選定的提案具有相同的值value。通過對提案編號的約定，它需要滿足以下保證：
P2. 如果具有value值v的提案被選定了，那么所有比它編號高的提案的value值也必須是v。

因為編號是完全有序的，所以條件P2就保證了只有一個value值被選定這一關(guān)鍵安全性屬性。

一個提案能被選定，必須要被至少一個Acceptor通過，所以我們可以通過滿足如下條件來滿足P2:

P2a. 如果一個具有value值v的提案被選定了，那么被Acceptor通過的所有編號比它高的提案的value值也必須是v。

我們?nèi)匀恍枰狿1來保證有提案會被選定。因為通信是異步的，一個提案可能會在某個Acceptor c還沒收到任何提案時就被選定了。假設(shè)有個新的Proposer蘇醒了，然后提出了一個具有不同value值的更高編號的提案，根據(jù)P1, 需要c通過這個提案，但這是與P2a相矛盾的。因此為了同時滿足P1和P2a，需要對P2a進行強化：

P2b. 如果具有value值v的提案被選定了，那么所有比它編號更高的被Proposer提出的提案的value值也必須是v。

一個提案被Acceptor通過之前肯定是由某個Proposer提出，因此P2b就隱含P2a，進而隱含了P2.

為了發(fā)現(xiàn)如何保證P2b，我們來看看如何證明它成立。我們假設(shè)某個具有編號m和value值v的提案被選定了，需要證明任意具有編號n（n > m）的提案都具有value值v。我們可以通過對n使用數(shù)學歸納法來簡化證明，這樣我們可以在額外的假設(shè)下——即編號在m..(n-1)之間的提案具有value值v，來證明編號為n的提案具有value值v，其中i..j表示從i到j(luò)的集合。因為編號為m的提案已經(jīng)被選定了，這就意味著存在一個多數(shù)Acceptor組成的集合C，C中的每個成員都通過了這個提案。結(jié)合歸納的假設(shè)，m被選定意味著：

C中的每一個Acceptor都通過了一個編號在m..(n-1)之間的提案，并且每個編號在m..(n-1)之間的被Acceptor通過的提案都具有value值v。

由于任何包含多數(shù)Acceptor的集合S都至少包含一個C中的成員，我們可以通過保持如下不變性來確保編號為n的提案具有value值v：

P2c. 對于任意v和n，如果一個編號為n，value值為v的提案被提出，那么肯定存在一個由多數(shù)Acceptor組成的集合S滿足以下條件中的一個：
    a. S中不存在任何Acceptor通過了編號小于n的提案
    b. v是S中所有Acceptor已經(jīng)通過的編號小于n的具有最大編號的提案的value值。

通過維護P2c的不變性我們就可以滿足P2b的條件了。

為了維護P2c的不變性，一個Proposer在提出編號為n的提案時，如果存在一個將要或者已經(jīng)被多數(shù)Acceptor通過的編號小于n的最大編號提案，Proposer需要知道它的信息。獲取那些已經(jīng)被通過的提案很簡單，但是預測未來會被通過的卻很困難。為了避免去預測未來，Proposer通過提出承諾不會有那樣的通過情況來控制它。換句話說，Proposer會請求那些Acceptor不要再通過任何編號小于n的提案了。這就導致了如下的提案生成算法：
Proposer選擇一個新的提案編號n，然后向某個Acceptor集合中的成員發(fā)送請示，要求它作出如下回應(yīng)：

    （a）保證不再通過任何編號小于n的提案。
    （b）當前它已經(jīng)通過的編號小于n的最大編號提案，如何存在的話。
 我們把這樣的請求稱為編號為n的prepare請求。

如果Proposer收到來自集合中多數(shù)成員的響應(yīng)結(jié)果，那么它可以提出編號為n，value值為v的提案，這里v是所有響應(yīng)中最大編號提案的value值，如果響應(yīng)中不包含任何提案，那么這個值就由Proposer自由決定。

Proposer通過向某個Acceptor集合發(fā)送需要被通過的提案請求來產(chǎn)生一個提案（這里的Acceptor集合不一定是響應(yīng)前一個請求的集合）。這們把這個叫做accept請求。

目前我們描述了Proposer端的算法。那么Acceptor端是怎樣的呢？它可能會收到來自Proposer端的兩種請求：prepare請求和accept請求。Acceptor可以忽略任意請求而不用擔心破壞算法的安全性。因此我們只需要說明它在什么情況下可以對一個請求作出響應(yīng)。它可以在任何時候響應(yīng)prepare請求也可以在不違反現(xiàn)有承諾的情況下響應(yīng)accept請求。換句話說：

P1a. 一個Acceptor可以通過一個編號為n的提案，只要它還未響應(yīng)任何編號大于n的prepare請求。

可以看出P1a包含了P1。

現(xiàn)在我們就獲得了一個滿足安全性需求的提案選定算法——假設(shè)在提案編號唯一的前提下。只要再做點小優(yōu)化，就能得到最終的算法了。
假設(shè)一個Acceptor收到了一個編號為n的prepare請求，但是它已經(jīng)對編號大于n的prepare請求作出了響應(yīng)，因此它肯定不會再通過任何新的編號為n的提案。那么它就沒有必要對這個請求作出響應(yīng)，因為它肯定不會通過編號為n的提案，于是我們會讓Acceptor忽略這樣的prepare請求，我們也會讓它忽略那些它已經(jīng)通過的提案的prepare請求。
通過這個優(yōu)化，Acceptor只需要記住它已經(jīng)通過的提案的最大編號以及它已經(jīng)響應(yīng)過prepare請求的提案的最大編號。因為必須要在出錯的情況下也保證P2c的不變性，所以Acceptor要在故障和重啟的情況下也能記住這些信息。Proposer可以隨時丟棄提案以及它的所有信息——只要它可以保證不會提出具有相同編號的提案即可。

把Proposer和Acceptor的行為結(jié)合起來，我們就能得到算法的如下兩階段執(zhí)行過程：
Phase 1:
Proposer選擇一個提案編號n，然后向Acceptor的多數(shù)集發(fā)送編號為n的prepare請求。
如果一個Acceptor收到一個編號為n的prepare請示，且n大于它所有已響應(yīng)請求的編號，那么它就會保證不會再通過任意編號小于n的提案，同時將它已經(jīng)通過的最大編號提案（如果存在的話）一并作為響應(yīng)。
Phase 2:
如果Proposer收到多數(shù)Acceptor對它prepare請求（編號為n）的響應(yīng)，那么它就會發(fā)送一個編號為n，value值為v的提案的accept請求給每個Acceptor，這里v是收到的響應(yīng)中最大編號提案的值，如果響應(yīng)中不包含任何提案，那么它就可以是任意值。
如果Acceptor收到一個編號為n的提案的accept請求，只要它還未對編號大于n的prepare作出響應(yīng)，它就可以通過這個提案。

一個Proposer可以提出多個提案，只要它能遵循以上算法約定。它可以在任意時刻丟棄某個提案（即使針對該提案的請求或響應(yīng)在提案丟棄后很久才到達，正確性依然可以保證）。如果Proposer已經(jīng)在嘗試提交更大編號的提案，那么丟棄也未嘗不是一件好事。因此，如果一個Acceptor因為已經(jīng)收到更高編號的prepare請求而忽略某個prepare或者accept請求，它應(yīng)該通知對應(yīng)的Proposer，然后該Proposer可以丟棄這個提案。這是一個不影響正確性的性能優(yōu)化。

為了獲取被選定的值，一個Learner必須要能知道一個提案已經(jīng)被多數(shù)Acceptor通過了。最直觀的算法是，讓每個Acceptor在通過一個提案時就通知所有Learner，把通過的提案告知它們。這可以讓Learner盡快找到被選定的值，但這需要每個Acceptor和Learner之間互相通信——通信次數(shù)等于二者數(shù)量的乘積。

在假設(shè)非拜占庭錯誤的前提下，一個Learner可以很容易地通過另一個Learner了解一個值已經(jīng)被選定了。我們可以讓所有Acceptor將它們的通過信息發(fā)送給一個特定的Learner，當一個value被選定時，由它來通知其他Learner。這種方法需要額外一個步驟才能通知到所有Learner，而且它也不是可靠的，因為那個特定的Learner可能會發(fā)生一些故障。但是這種情況下的通信次數(shù)，只需要二者數(shù)量之和。

更一般地，Acceptor可以將它們的通過信息發(fā)送給一個特寫的Learner集合，它們中的任何一個都可以在某個value被選定后通知所有Learner。這個集合中的Learner越多，可靠性就越好，通信復雜度也相應(yīng)更高。

因為消息可能會丟失，一個value被選定后，可能沒有Learner會發(fā)現(xiàn)。Learner可以向Acceptor詢問它們通過了哪些提案，但是任一Acceptor出錯，都有可能導致無法分辨是否有多數(shù)Acceptor通過了某個提案。在這種情況下，只有當一個新的提案被選定時，Learner才能發(fā)現(xiàn)被選定的value。如果一個Learner想知道是否已經(jīng)選定一個value，它可以讓Proposer利用上面的算法提出一個提案。

很容易可以構(gòu)造出這樣一種情況，兩個Proposer持續(xù)地提出序號遞增的提案，但是沒有提案會被選定。Proposer p為編號為n1的提案完成Phase 1, 然后另一個Proposer q為編號為n2(n2>n1)的提案完成Phase 1。Proposer p對于編號n1的Phase 2的accept請求會被忽略，因為Acceptor承諾不再通過任何編號小于n2的提案。這樣Proposer p就會用一個新的編號n3(n3>n2)重新開始并完成Phase 1，這又導致了Proposer q對于Phase 2的accept請求被忽略，如此往復。

為了保證進度，必須選擇一個特定的Proposer作為唯一的提案提出者。如果這個Proposer可以和多數(shù)Acceptor進行通信，并且可以使用比已用編號更大的編號來進行提案的話，那么它提出的提案就可以成功被通過。如果知道有某些編號更高的請求，它可以通過舍棄當前的提案并重新開始，這個Proposer最終一定會選到一個足夠大的提案編號。

如果系統(tǒng)中有足夠的組件（Proposer, Acceptor以及網(wǎng)絡(luò)通信）工作良好，通過選舉一個特定的Proposer，活性就能夠達到。著名的FLP理論[1]指出，一個可靠的Proposer選舉算法要么利用隨時性要么利用實時性來實現(xiàn)——比如使用超時機制。然而無論選舉是否成功，安全性都可以保證。

Paxos算法[5]假設(shè)了一組進程網(wǎng)絡(luò)。在它的一致性算法中，每個進程都扮演著Proposer, Acceptor以及Learner的角色。該算法選擇了一個Leader來扮演那個特定的Proposer和Learner。Paxos一致性算法就是上面描述的那個，請求和響應(yīng)都以普通消息的方式發(fā)送（響應(yīng)消息通過對應(yīng)的提案編號來標識以避免混淆）。使用可靠的存儲設(shè)備存儲Acceptor需要記住的信息來防止出錯。Acceptor在真正發(fā)送響應(yīng)之前，會將它記錄到可靠的存儲設(shè)備中。

剩下的就是描述如果保證不會用到重復編號的機制了。不同的Proposer從不相交的編號集合中選擇自己的編號，這樣任何兩個Proposer就不會用到相同的編號了。每個Proposer都記錄（在可靠存儲設(shè)備中）它使用過的最大編號，然后用比這更大編號的提案開始Phase 1。

有一種實現(xiàn)分布式系統(tǒng)的簡單方式，就是使用一組客戶端集合向中央服務(wù)器發(fā)送命令。服務(wù)器可以看成一個以某種順序執(zhí)行客戶端命令的確定性狀態(tài)機。這個狀態(tài)機有個當前狀態(tài)，通過接收一個命令當作輸入來產(chǎn)生一個輸出和新狀態(tài)。比如，分布式銀行系統(tǒng)的客戶端可能是一些出納員，狀態(tài)機的狀態(tài)則由所有用戶的賬戶余額組成。一個取款操作，通過執(zhí)行一個減少賬戶余額的狀態(tài)機命令（當且僅當余額大于取款數(shù)目時）實現(xiàn)，然后將新舊余額作為輸出。

使用單點中央服務(wù)器的系統(tǒng)在該服務(wù)器故障的情況下，整個系統(tǒng)都將運行失敗。因此我們用一組服務(wù)器來代替它，每個服務(wù)器都獨立實現(xiàn)了該狀態(tài)機。因為這個狀態(tài)機是確定性的，如果所有服務(wù)器都以同樣的順序執(zhí)行命令，那么它們將產(chǎn)生相同的狀態(tài)機狀態(tài)和輸出。一個提出命令的客戶端，可以使用任意服務(wù)器為它產(chǎn)生的輸出。

為了保證所有服務(wù)器都能執(zhí)行相同的狀態(tài)機命令序列，我們需要實現(xiàn)一系列獨立的Paxos一致性算法實例，第i個實例選定的值作為序列中的第i個狀態(tài)機命令。在算法的每個實例中，每個服務(wù)器擔任所有角色（Proposer，Acceptor和Learner）。現(xiàn)在，我們假設(shè)服務(wù)器的集合是固定的，這樣所有的一致性算法實例都具有相同的參與者集合。

在正常執(zhí)行中，一個服務(wù)器被選舉成為Leader，它會在所有一致性算法實例當中扮演特定的Proposer（唯一的提案提出者）。客戶端給Leader發(fā)送命令，它來決定每條命令出現(xiàn)在序列當中的位置。如果Leader決定某個客戶端命令應(yīng)該是第135個，它會嘗試讓該命令成為第135個一致性算法實例選定的value值。這通常都會成功，但是在一些故障或者有另外的服務(wù)器也認為自己是Leader并且對第135個命令持有異議時，它可能會失敗。但是一致性算法可以保證，最多只有一條命令會被選定為第135條。

這個方法的關(guān)鍵在于，在Paxos一致性算法中，被提出的value值只在Phase 2才會被選定。回憶一下，在Proposer完成Phase 1時，要么提案的value值被確定了，要么Proposer可以自由提出任意值。

我們現(xiàn)在描述了Paxos狀態(tài)機實現(xiàn)是怎樣在正常情況下運行的，接下來我們看看會有哪些出錯的情況，看下之前的Leader故障以及新的Leader被選舉出來后會發(fā)生什么（系統(tǒng)啟動是一種特殊情況，此時還沒有命令被提出）。

新的Leader被選舉出來后，首先要成為所有一致性算法實例的Learner，需要知道目前已經(jīng)選定的大部分命令。假設(shè)它知道命令1-134，138以及139——也就是一致性算法實例1-134，138以及139選定的值（后面我們會看到這樣的命令缺口是如何產(chǎn)生的）。接下來它會執(zhí)行135-137以及139以后的算法實例的Phase 1（下面會描述如何來做）。假設(shè)執(zhí)行結(jié)果表明，實例135和140的提案值已被確定，但是其他執(zhí)行實例的提案值是沒有限制的。那么Leader可以執(zhí)行實例135和140的Phase 2，進而選定第135和140條命令。

Leader以及其他已經(jīng)獲取Leader所有已知命令的服務(wù)器，現(xiàn)在可以執(zhí)行命令1-135。然而它還不能執(zhí)行命令138-140，因為命令136和137還未被選定。Leader可以將接下來兩條客戶端請求的命令當作命令136和137。同時我們也可以提出一個特殊的“noop”指令來立即填補這個空缺但保持狀態(tài)不變（通過執(zhí)行一致性算法實例136和137的Phase 2來完成）。一旦該no-op指令被選定，命令138-140就可以被執(zhí)行了。

命令1-140目前已經(jīng)被選定了。Leader也已經(jīng)完成了所有大于140的一致性算法實例的Phase 1，而且它可以在Phase 2中自由地為這些實例指定任意值。它為下一個從客戶端接收的命令分配序號141， 并在Phase 2中將它作為第141個一致性算法實例的value值。它將接收到的下一個客戶端命令作為命令142, 并以此類推。

Leader可以在它提出的命令141被選定前提出命令142。它發(fā)送的關(guān)于命令141的提案信息可能全部丟失，因此在所有其他服務(wù)器獲知Leader選定的命令141之前，命令142就可能已被選定。當Leader無法收到實例141的Phase 2的期望回應(yīng)時，它會重傳這些信息。如果一切順利的話，它的提案命令將被選定。但是仍然可能會失敗，造成在選定的命令序列中出現(xiàn)缺口。一般來說，假設(shè)Leader可以提前確定a個命令，這意味著命令i被選定之后，它就可以提出i+1到i+a的命令了。這樣就可能形成長達a-1的命令缺口。

一個新選定的Leader需要為無數(shù)個一致性算法實例執(zhí)行Phase 1——在上面的場景中，就是135-137以及所有大于139的執(zhí)行實例。通過向其他服務(wù)器發(fā)送一條合適的消息，就可以讓所有執(zhí)行實例使用同一個提案編號（計數(shù)器）。在Phase 1中，只要一個Acceptor已經(jīng)收到來自某Proposer的Phase 2消息，那么它就可以為不止一個實例作出通過回應(yīng)（在上面的場景中，就是針對135和140的情況）。因此一個服務(wù)器（作為Acceptor時）可以用一條適當?shù)亩滔λ袑嵗鞒龌貞?yīng)。執(zhí)行這樣無限多的實例的Phase 1也不會有問題。
這里應(yīng)該是指穩(wěn)定的Paxos模型，Phase 1可以被省略，只要編號計數(shù)器是唯一的。

由于Leader的故障和新Leader的選舉是很少見的情況，那么執(zhí)行一條狀態(tài)機命令的主要開銷，即在命令值上達成一致性的開銷，就是執(zhí)行一致性算法中Phase 2的開銷。可以證明，在允許失效的情況下，Paxos一致性算法的Phase 2在所有一致性算法中具有最小可能的時間復雜度[2]。因此Paxos算法基本上是最優(yōu)的。

在系統(tǒng)正常運行的情況下，我們假設(shè)總是只有一個Leader，只有在當前Leader故障及選舉出新Leader之間的短時間內(nèi)才會違背這個假設(shè)。在特殊情況下，Leader選舉可能失敗。如果沒有服務(wù)器扮演Leader，那么就沒有新命令被提出。如果同時有多個服務(wù)器認為自己是Leader，它們在一個一致性算法執(zhí)行實例中可能提出不同value值，這可能導致沒有任何值能被選定。但是安全性是可以保證的——不可能有兩個不同的值被選定為第i條狀態(tài)機命令。單個Leader的選舉只是為了保證流程能往下進行。

如果服務(wù)器的集合是變化的，那么必須有某種方法可以決定哪些服務(wù)器來實現(xiàn)哪一些一致性算法實例。最簡單的方式就是通過狀態(tài)機本身來完成。當前的服務(wù)器集合可以是狀態(tài)的一部分，同時也可以通過狀態(tài)機命令來改變。通過用執(zhí)行完第i條狀態(tài)機命令后的狀態(tài)來描述執(zhí)行一致性算法i+a的服務(wù)器集合，我們就能讓Leader提前獲取a個狀態(tài)機命令。這就允許任意復雜的重配置算法有一個簡單實現(xiàn)。

參與文獻

[1]    Michael J. Fischer, Nancy Lynch, and Michael S. Paterson.
Impossibility of distributed consensus with one faulty process.
Journal of the ACM, 32(2):374–382, April 1985. [2]    Idit Keidar and
Sergio Rajsbaum. On the cost of fault-tolerant consensus when there
are no faults—a tutorial. TechnicalReport MIT-LCS-TR-821, Laboratory
for Computer Science, Massachusetts Institute Technology, Cambridge,
MA, 02139, May 2001. also published in SIGACT News 32(2) (June 2001).
[3]    Leslie Lamport. The implementation of reliable distributed
multiprocess systems. Computer Networks, 2:95–114, 1978. [4]    Leslie
Lamport. Time, clocks, and the ordering of events in a distributed
system. Communications of the ACM, 21(7):558–565, July 1978. [5]    (1,
2, 3, 4) Leslie Lamport. The part-time parliament. ACM Transactions on
Computer Systems, 16(2):133–169, May 1998.