Can you summarize the following document?
        
  分散式系統中的節點通訊存在兩種模型:共享記憶體(Shared memory)和訊息傳遞(Messages passing)。基於訊息傳遞通訊模型的分散式系統,不可避免的會發生以下錯誤:程序可能會慢、被殺死或者重啟,訊息可能會延遲、丟失、重複,在基礎 Paxos 場景中,先不考慮可能出現訊息篡改即拜占庭錯誤的情況。Paxos 演算法解決的問題是在一個可能發生上述異常的分散式系統中如何就某個值達成一致,保證不論發生以上任何異常,都不會破壞決議的共識。一個典型的場景是,在一個分散式資料庫系統中,如果各節點的初始狀態一致,每個節點都執行相同的操作序列,那麼他們最後能得到一個一致的狀態。為保證每個節點執行相同的命令序列,需要在每一條指令上執行一個「共識演算法」以保證每個節點看到的指令一致。一個通用的共識演算法可以應用在許多場景中,是分散式計算中的重要問題。因此從20世紀80年代起對於共識演算法的研究就沒有停止過。  為描述Paxos演算法,Lamport虛擬了一個叫做Paxos的希臘城邦,這個島按照議會民主制的政治模式制訂法律,但是沒有人願意將自己的全部時間和精力放在這種事情上。所以無論是議員,議長或者傳遞紙條的服務員都不能承諾別人需要時一定會出現,也無法承諾批准決議或者傳遞訊息的時間。但是這裡假設沒有拜占庭將軍問題(Byzantine failure,即雖然有可能一個訊息被傳遞了兩次,但是絕對不會出現錯誤的訊息);只要等待足夠的時間,訊息就會被傳到。另外,Paxos島上的議員是不會反對其他議員提出的決議的。  對應於分散式系統,議員對應於各個節點,制定的法律對應於系統的狀態。各個節點需要進入一個一致的狀態,例如在獨立Cache的對稱多處理器系統中,各個處理器讀記憶體的某個位元組時,必須讀到同樣的一個值,否則系統就違背了一致性的要求。一致性要求對應於法律條文只能有一個版本。議員和服務員的不確定性對應於節點和訊息傳遞通道的不可靠性。

  

  首先將議員的角色分為 proposers,acceptors,和 learners(允許身兼數職)。proposers 提出提案,提案資訊包括提案編號和提議的 value;acceptor 收到提案後可以接受(accept)提案,若提案獲得多數派(majority)的 acceptors 的接受,則稱該提案被批准(chosen);learners 只能「學習」被批准的提案。劃分角色後,就可以更精確的定義問題:  另外還需要保證 progress。這一點以後再討論。  作者通過不斷加強上述3個約束(主要是第二個)獲得了 Paxos 演算法。  批准 value 的過程中,首先 proposers 將 value 傳送給 acceptors,之後 acceptors 對 value 進行接受(accept)。為了滿足只批准一個 value 的約束,要求經「多數派(majority)」接受的 value 成為正式的決議(稱為「批准」決議)。這是因為無論是按照人數還是按照權重劃分,兩組「多數派」至少有一個公共的 acceptor,如果每個 acceptor 只能接受一個 value,約束2就能保證。  於是產生了一個顯而易見的新約束:  注意 P1 是不完備的。如果恰好一半 acceptor 接受的提案具有 value A,另一半接受的提案具有 value B,那麼就無法形成多數派,無法批准任何一個 value。  約束2並不要求只批准一個提案,暗示可能存在多個提案。只要提案的 value 是一樣的,批准多個提案不違背約束2。於是可以產生約束 P2:  注:通過某種方法可以為每個提案分配一個編號,在提案之間建立一個全序關係,所謂“之後”都是指所有編號更大的提案。  如果 P1 和 P2 都能夠保證,那麼約束2就能夠保證。  批准一個 value 意味著多個 acceptor 接受(accept)了該 value。因此,可以對 P2 進行加強:  由於通訊是非同步的,P2a 和 P1 會發生衝突。如果一個 value 被批准後,一個 proposer 和一個 acceptor 從休眠中甦醒,前者提出一個具有新的 value 的提案。根據 P1,後者應當接受,根據 P2a,則不應當接受,這種場景下 P2a 和 P1 有矛盾。於是需要換個思路,轉而對 proposer 的行為進行約束:  由於 acceptor 能接受的提案都必須由 proposer 提出,所以 P2b 蘊涵了 P2a,是一個更強的約束。  但是根據 P2b 難以提出實現手段。因此需要進一步加強 P2b。  假設一個編號為 m 的 value v 已經獲得批准(chosen),來看看在什麼情況下對任何編號為 n(n>m)的提案都含有 value v。因為 m 已經獲得批准(chosen),顯然存在一個 acceptors 的多數派 C,他們都接受(accept)了v。考慮到任何多數派都和 C 具有至少一個公共成員,可以找到一個蘊涵 P2b 的約束 P2c:  可以用數學歸納法證明 P2c 蘊涵 P2b:  假設具有value v的提案m獲得批准,當n=m+1時,採用反證法,假如提案n不具有value v,而是具有value w,根據P2c,則存在一個多數派S1,要麼他們中沒有人接受過編號小於n的任何提案,要麼他們已經接受的所有編號小於n的提案中編號最大的那個提案是value w。由於S1和通過提案m時的多數派C之間至少有一個公共的acceptor,所以以上兩個條件都不成立,匯出矛盾從而推翻假設,證明了提案n必須具有value v;  若(m+1)..(N-1)所有提案都具有value v,採用反證法,假如新提案N不具有value v,而是具有value w',根據P2c,則存在一個多數派S2,要麼他們沒有接受過m..(N-1)中的任何提案,要麼他們已經接受的所有編號小於N的提案中編號最大的那個提案是value w'。由於S2和通過m的多數派C之間至少有一個公共的acceptor,所以至少有一個acceptor曾經接受了m,從而也可以推出S2中已接受的所有編號小於n的提案中編號最大的那個提案的編號範圍在m..(N-1)之間,而根據初始假設,m..(N-1)之間的所有提案都具有value v,所以S2中已接受的所有編號小於n的提案中編號最大的那個提案肯定具有value v,匯出矛盾從而推翻新提案n不具有value v的假設。根據數學歸納法,我們證明了若滿足P2c,則P2b一定滿足。  P2c是可以通過訊息傳遞模型實現的。另外,引入了P2c後,也解決了前文提到的P1不完備的問題。

  要滿足P2c的約束,proposer提出一個提案前,首先要和足以形成多數派的acceptors進行通訊,獲得他們進行的最近一次接受(accept)的提案(prepare過程),之後根據回收的資訊決定這次提案的value,形成提案開始投票。當獲得多數acceptors接受(accept)後,提案獲得批准(chosen),由acceptor將這個訊息告知learner。這個簡略的過程經過進一步細化後就形成了Paxos演算法。  在一個paxos例項中,每個提案需要有不同的編號,且編號間要存在全序關係。可以用多種方法實現這一點,例如將序數和proposer的名字拼接起來。如何做到這一點不在Paxos演算法討論的範圍之內。  如果一個沒有chosen過任何proposer提案的acceptor在prepare過程中回答了一個proposer針對提案n的問題,但是在開始對n進行投票前,又接受(accept)了編號小於n的另一個提案(例如n-1),如果n-1和n具有不同的value,這個投票就會違背P2c。因此在prepare過程中,acceptor進行的回答同時也應包含承諾:不會再接受(accept)編號小於n的提案。這是對P1的加強:  現在已經可以提出完整的演算法了。

  通過一個決議分為兩個階段:  這個過程在任何時候中斷都可以保證正確性。例如如果一個proposer發現已經有其他proposers提出了編號更高的提案,則有必要中斷這個過程。因此為了優化,在上述prepare過程中,如果一個acceptor發現存在一個更高編號的提案,則需要通知proposer,提醒其中斷這次提案。

  用實際的例子來更清晰地描述上述過程:  有A1, A2, A3, A4, A5 5位議員,就稅率問題進行決議。議員A1決定將稅率,因此它向所有人發出一個草案。這個草案的內容是:  在最簡單的情況下,沒有人與其競爭;資訊能及時順利地傳達到其它議員處。  於是, A2-A5迴應:  而A1在收到2份回覆後就釋出最終決議:  這實際上退化為二階段提交協議。  現在我們假設在A1提出提案的同時, A5決定將稅率定為20%:  草案要通過侍從送到其它議員的案頭. A1的草案將由4位侍從送到A2-A5那裡。現在,負責A2和A3的侍從將草案順利送達,負責A4和A5的侍從則不上班. A5的草案則順利的送至A4和A3手中。  現在, A1, A2, A3收到了A1的提案; A4, A3, A5收到了A5的提案。按照協議, A1, A2, A4, A5將接受他們收到的提案,侍從將拿著  的回覆回到提案者那裡。  而A3的行為將決定批准哪一個。  在討論之前我們要明確一點,提案是全域性有序的。在這個示例中,是說每個提案提出的日期都不一樣。即第3年3月15日只有A1的提案;第3年3月16日只有A5的提案。不可能在某一天存在兩個提案。

  假設A1的提案先送到A3處,而A5的侍從決定放假一段時間。於是A3接受並派出了侍從. A1等到了兩位侍從,加上它自己已經構成一個多數派,於是稅率10%將成為決議. A1派出侍從將決議送到所有議員處:  A3在很久以後收到了來自A5的提案。由於稅率問題已經討論完畢,開始討論某些議員在第3年3月17日提出的議案。因此這個3月16日提出的議案他不去理會。他自言自語地抱怨一句:

  依然假設A1的提案先送到A3處,但是這次A5的侍從不是放假了,只是中途耽擱了一會。這次, A3依然會將"接受"回覆給A1.但是在決議成型之前它又收到了A5的提案。則:  1.如果A5提案的提出時間比A1的提案更晚一些,這裡確實滿足這種情況,因為3月16日晚於3月15日。,則A3回覆:  於是, A1和A5都收到了足夠的回覆。這時關於稅率問題就有兩個提案在同時進行。但是A5知道之前有人提出稅率為10%.於是A1和A5都會向全體議員廣播:  共識到了保證。  2. 如果A5提案的提出時間比A1的提案更早一些。假設A5的提案是3月14日提出,則A3直接不理會。

  一個顯而易見的方法是當acceptors批准一個value時,將這個訊息傳送給所有learners。但是這個方法會導致訊息量過大。  由於假設沒有Byzantine failures,learners可以通過別的learners獲取已經通過的決議。因此acceptors只需將批准的訊息傳送給指定的某一個learner,其他learners向它詢問已經通過的決議。這個方法降低了訊息量,但是指定learner失效將引起系統失效。  因此acceptors需要將accept訊息傳送給learners的一個子集,然後由這些learners去通知所有learners。  但是由於訊息傳遞的不確定性,可能會沒有任何learner獲得了決議批准的訊息。當learners需要了解決議通過情況時,可以讓一個proposer重新進行一次提案。注意一個learner可能兼任proposer。

  根據上述過程當一個proposer發現存在編號更大的提案時將終止提案。這意味著提出一個編號更大的提案會終止之前的提案過程。如果兩個proposer在這種情況下都轉而提出一個編號更大的提案,就可能陷入活鎖,違背了Progress的要求。一般活鎖可以通過 隨機睡眠-重試 的方法解決。這種情況下的解決方案是選舉出一個leader,僅允許leader提出提案。但是由於訊息傳遞的不確定性,可能有多個proposer自認為自己已經成為leader。Lamport在The Part-Time Parliament一文中描述並解決了這個問題。

  Paxos的典型部署需要一組連續的被接受的值(value),作為應用到一個分散式狀態機的一組命令。如果每個命令都通過一個Basic Paxos演算法例項來達到一致,會產生大量開銷。  如果Leader是相對穩定不變的,第1階段就變得不必要。 這樣,系統可以在接下來的Paxos演算法例項中,跳過的第1階段,直接使用同樣的Leader。  為了實現這一目的,在同一個Leader執行每輪Paxos演算法時,提案編號 I 每次遞增一個值,並與每個值一起傳送。Multi-Paxos在沒有故障發生時,將訊息延遲(從propose階段到learn階段)從4次延遲降低為2次延遲。

  

  在下面的圖中,只顯示了基本Paxos協議的一個例項(或“執行”)和一個初始Leader(Proposer)。注意,Multi-Paxos使用幾個Basic Paxos的例項。  式中V = (Va, Vb, Vc) 中最新的一個。

  在這種情況下,Basic Paxos的後續例項(由I+1表示)使用相同的Leader,因此,包含在Prepare和Promise的階段1(Basic Paxos協議的這些後續例項)將被跳過。注意,這裡要求Leader應該是穩定的,即它不應該崩潰或改變。

  Fast-Paxos將Basic-Paxos進行了推廣,以減少端到端訊息延遲。在Basic-Paxos中,從客戶端發起請求開始,到Learn階段結束的訊息延遲是3個訊息延遲。而Fast-Paxos允許2個訊息延遲,但要求:  (1)系統由"3f+ 1"個Acceptor組成,以容忍最多"f"個錯誤(而不是Basic-Paxos的"2f+1");  (2)客戶端需要直接將請求傳送到多個目標。  直觀上,如果Leader沒有提議任何value,那麼客戶可以直接傳送"Accept"訊息到向接收方發。Acceptor會像Basic-Paxos一樣執行,向Leader和每個Learner傳送"Accepted"的訊息,從而實現從客戶端到Learner的兩訊息延遲。  如果Leader檢測到衝突,它通過發起新一輪投票,併傳送"Accept"訊息來解決衝突,通常是一個"Accepted"訊息。這種有協調者參與的衝突恢復機制需要4個從客戶端到Learner的訊息延遲。  如果Leader提前指定了一種衝突恢復機制,就可以實現另一種優化,它允許Acceptors自己執行衝突恢復。因此,無協調的衝突恢復可能實現三個訊息延遲(如果所有的Learner都是接收者,那麼只有兩個訊息延遲)。

  有協調這參與的衝突恢復。注意:協議沒有指定如何處理被丟棄的客戶端請求。  無協調者參與的相沖突恢復:

  微軟公司為簡化的Paxos演算法申請了專利。但專利中公開的技術和本文所描述的不盡相同。  谷歌公司(Google公司)在其分散式鎖服務中應用了Multi-Paxos演算法。Chubby lock應用於大表(Bigtable),後者在谷歌公司所提供的各項服務中得到了廣泛的應用。  谷歌公司(Google公司)在其分散式資料庫spanner中使用Multi-Paxos作為分散式共識保證的基礎元件 Apache ZooKeeper 使用一個類Multi-Paxos的共識演算法作為底層儲存協同的機制。
Paxos演算法是萊斯利·蘭伯特(英語:Leslie Lamport,LaTeX中的「La」)於1990年提出的一種基於訊息傳遞且具有高度容錯特性的共識(consensus)演算法。