背景

在計算機通信理論中，有一個著名的兩軍問題(two-army problem)，講述通信的雙方通過ACK來達成共識，永遠會有一個在途的ACK需要進行確認，因此無法達成共識。

兩軍問題和Basic Paxos非常相似

1） 通信的各方需要達成共識；

2） 通信的各方僅需要達成一個共識；

3） 假設的前提是信道不穩定，有丟包、延遲或者重放，但消息不會被篡改。

Basic Paxos最早以希臘議會的背景來講解，但普通人不理解希臘議會的運作模式，因此看Basic Paxos的論文會比較難理解。兩軍問題的背景大家更熟悉，因此嘗試用這個背景來演繹一下Basic Paxos。

為了配合Basic Paxos的多數派概念，把兩軍改為3軍；同時假設了將軍和參謀的角色。

假設的3軍問題

1） 1支紅軍在山谷里扎營，在周圍的山坡上駐扎著3支藍軍；

2） 紅軍比任意1支藍軍都要強大；如果1支藍軍單獨作戰，紅軍勝；如果2支或以上藍軍同時進攻，藍軍勝；

3） 三支藍軍需要同步他們的進攻時間；但他們惟一的通信媒介是派通信兵步行進入山谷，在那里他們可能被俘虜，從而將信息丟失；或者為了避免被俘虜，可能在山谷停留很長時間；

4） 每支軍隊有1個參謀負責提議進攻時間；每支軍隊也有1個將軍批準參謀提出的進攻時間；很明顯，1個參謀提出的進攻時間需要獲得至少2個將軍的批準才有意義；

5） 問題：是否存在一個協議，能夠使得藍軍同步他們的進攻時間？

接下來以兩個假設的場景來演繹BasicPaxos；參謀和將軍需要遵循一些基本的規則

1） 參謀以兩階段提交（prepare/commit）的方式來發起提議，在prepare階段需要給出一個編號；

2） 在prepare階段產生沖突，將軍以編號大小來裁決，編號大的參謀勝出；

3） 參謀在prepare階段如果收到了將軍返回的已接受進攻時間，在commit階段必須使用這個返回的進攻時間；

兩個參謀先后提議的場景

1） 參謀1發起提議，派通信兵帶信給3個將軍，內容為（編號1）；

2） 3個將軍收到參謀1的提議，由于之前還沒有保存任何編號，因此把（編號1）保存下來，避免遺忘；同時讓通信兵帶信回去，內容為（ok）；

3） 參謀1收到至少2個將軍的回復，再次派通信兵帶信給3個將軍，內容為（編號1，進攻時間1）；

4） 3個將軍收到參謀1的時間，把（編號1，進攻時間1）保存下來，避免遺忘；同時讓通信兵帶信回去，內容為（Accepted）；

5） 參謀1收到至少2個將軍的（Accepted）內容，確認進攻時間已經被大家接收；

6） 參謀2發起提議，派通信兵帶信給3個將軍，內容為（編號2）；

7） 3個將軍收到參謀2的提議，由于（編號2）比（編號1）大，因此把（編號2）保存下來，避免遺忘；又由于之前已經接受參謀1的提議，因此讓通信兵帶信回去，內容為（編號1，進攻時間1）；

8） 參謀2收到至少2個將軍的回復，由于回復中帶來了已接受的參謀1的提議內容，參謀2因此不再提出新的進攻時間，接受參謀1提出的時間；

兩個參謀交叉提議的場景

1） 參謀1發起提議，派通信兵帶信給3個將軍，內容為（編號1）；

2） 3個將軍的情況如下

a) 將軍1和將軍2收到參謀1的提議，將軍1和將軍2把（編號1）記錄下來，如果有其他參謀提出更小的編號，將被拒絕；同時讓通信兵帶信回去，內容為（ok）；

b) 負責通知將軍3的通信兵被抓，因此將軍3沒收到參謀1的提議；

3） 參謀2在同一時間也發起了提議，派通信兵帶信給3個將軍，內容為（編號2）；

4） 3個將軍的情況如下

a) 將軍2和將軍3收到參謀2的提議，將軍2和將軍3把（編號2）記錄下來，如果有其他參謀提出更小的編號，將被拒絕；同時讓通信兵帶信回去，內容為（ok）；

b) 負責通知將軍1的通信兵被抓，因此將軍1沒收到參謀2的提議；

5） 參謀1收到至少2個將軍的回復，再次派通信兵帶信給有答復的2個將軍，內容為（編號1，進攻時間1）；

6） 2個將軍的情況如下

a) 將軍1收到了（編號1，進攻時間1），和自己保存的編號相同，因此把（編號1，進攻時間1）保存下來；同時讓通信兵帶信回去，內容為（Accepted）；

b) 將軍2收到了（編號1，進攻時間1），由于（編號1）小于已經保存的（編號2），因此讓通信兵帶信回去，內容為（Rejected，編號2）；

7） 參謀2收到至少2個將軍的回復，再次派通信兵帶信給有答復的2個將軍，內容為（編號2，進攻時間2）；

8） 將軍2和將軍3收到了（編號2，進攻時間2），和自己保存的編號相同，因此把（編號2，進攻時間2）保存下來，同時讓通信兵帶信回去，內容為（Accepted）；

9） 參謀2收到至少2個將軍的（Accepted）內容，確認進攻時間已經被多數派接受；

10） 參謀1只收到了1個將軍的（Accepted）內容，同時收到一個（Rejected，編號2）；參謀1重新發起提議，派通信兵帶信給3個將軍，內容為（編號3）；

11） 3個將軍的情況如下

a) 將軍1收到參謀1的提議，由于（編號3）大于之前保存的（編號1），因此把（編號3）保存下來；由于將軍1已經接受參謀1前一次的提議，因此讓通信兵帶信回去，內容為（編號1，進攻時間1）；

b) 將軍2收到參謀1的提議，由于（編號3）大于之前保存的（編號2），因此把（編號3）保存下來；由于將軍2已經接受參謀2的提議，因此讓通信兵帶信回去，內容為（編號2，進攻時間2）；

c) 負責通知將軍3的通信兵被抓，因此將軍3沒收到參謀1的提議；

12） 參謀1收到了至少2個將軍的回復，比較兩個回復的編號大小，選擇大編號對應的進攻時間作為最新的提議；參謀1再次派通信兵帶信給有答復的2個將軍，內容為（編號3，進攻時間2）；

13） 將軍1和將軍2收到了（編號3，進攻時間2），和自己保存的編號相同，因此保存（編號3，進攻時間2），同時讓通信兵帶信回去，內容為（Accepted）；

14） 參謀1收到了至少2個將軍的（accepted）內容，確認進攻時間已經被多數派接受；

小結

BasicPaxos算法難理解，除了講故事的背景不熟悉之外，還有以下幾點

1） 參與的各方并不是要針鋒相對，拼個你死我活；而是要合作共贏，最終達成一個共識；當大家講起投票的時候，往往第一反應是要針鋒相對，沒想到是要合作共贏；很明顯可以想到，在第二個場景下，如果參謀1為了逞英雄，強行要提交他提出的進攻時間1，那么最終是無法達成一個共識的；這里的點就在于參謀1違反了規則，相當于產生了拜占庭錯誤；

2） 常規的通信協議設計，對于寫操作，通常都是只返回成功和失敗的狀態，不會返回更多的東西；但BasicPaxos的prepare和commit，將軍除了返回成功還是失敗的狀態之外，還會把之前已經發生的一些狀態帶回給參謀，這個和常規的通信協議是不同的；

3） 在兩軍問題的背景下，其實知道進攻時間被至少2個將軍接受的是參謀，而不是將軍；在“兩個參謀交叉提議的場景”下，當參謀1沒有做第2次prepare之前，將軍1記錄的其實是一個錯誤的進攻時間；理論上來說，任何一個將軍在任何一個時刻都無法判斷自己不是處在將軍1的場景下；因此BasicPaxos在3個藍軍組成的系統中達成了一個共識，但并沒有為每個將軍明確了共識；

4） 本文的兩個場景都以“兩個參謀”來講，這里的“兩個參謀”可能是真的兩個不同的參謀，也可能是同一個參謀因為某種原因先后做了多次提議；對應分布式系統的場景

a） 真的有兩個并發的client

b） 兩個client一先一后；第一個client執行到某個步驟因為某種原因停止了；過了一段時間，另外一個client接著操作同一個數據

c） 同一個client重試；第一次執行到某一步驟因為某種原因停止了，立即或者稍后進行了重試

后記

寫這篇文章的時候，參考了以下兩篇文章。

Paxos算法細節詳解(一)--通過現實世界描述算法

http://www.cnblogs.com/endsock/p/3480093.html

第一篇文章用了我們喜聞樂見的背景，大部分內容非常容易理解，尤其是用比特幣來映射編號，非常貼切；只是對于proposer-1小姐最后的“背叛”會有點違反常識。看完這個故事之后就一直在想更貼切的背景。在兩軍問題中，藍軍各方是要合作達成一個共識；對于參謀來說，獲得了前一個參謀的提議就接受，而不再提出自己的提議是符合邏輯的，這個和paxos也更加吻合。在實際的分布式系統中，如果遇到沖突，涉及的各方也不是要針鋒相對爭個你死我活，想要的只是能發現沖突，只有一方成功、或者全部失敗都無所謂，只要能保證數據一致就行。

以兩軍問題為背景，在提議編號上找不到合適的映射點，比較生硬，這一點不如第一遍文章中的故事。

Question 7: The Two Generals’ Problem of reaching consensus on when to attack is unsolvable, how come it’s possible to have consensus with Paxos?

http://bogdan.pistol.gg/2014/10/20/paxos-algorithm-explained-part-2-insights/#q7

paxos最終仍然無法解決兩軍問題，即使是擴展到3軍也是無法解決的。在3軍背景下，按paxos算法的定義，最后是達成了一個共同的進攻時間，3軍中的任何一方都可以通過paxos算法讀取出這個進攻時間。但3軍怎么知道在什么時候去讀取、其他人是否已經讀取，這是一個和兩軍問題同樣的問題；同時由于通信兵可能無限延遲，可能部分藍軍在進攻時間之前讀取到了，部分藍軍可能在進攻時間之后才讀取到，所以兩軍最終還是無解的。第二篇參考文章中也詳細描述了這些問題。所以寫paxos和兩軍問題，不是說paxos解決了兩軍問題，只是借用兩軍問題的背景來演繹paxos。