概述
《Distributed consensus revised》是 Heidi Howard 寫於 2019年4月份的博士論文。該論文主要是針對 Paxos 算法的改進，主要改進的地方是在減少和 quorums 交互的情況下使算法對某一個提議達成共識。傳統的 Paxos 算法實現上，無論哪個階段都需要滿足節點的大多數。論文中提到到的 a b c 改進算法只需 phase one 和 phase two 階段有交集，並且每個改進的算法都在依次減少這個交集中的 quorums 數量。且在此算法基礎上，每個節點在提交提案的時候都能 skip phase one 和共享 epochs 下高效地到達共識。
下面將對論文中提及到的 Quorum intersection、Promise、value selection 和 Epochs 改進分別做個大概的描述，具體的改進描述大家可以參考論文。除此以外，讀者需要對 classic paxos 算法有一定的瞭解。
01 Quorum intersection Revised
我們知道，Classic Paxos 是兩階段提交協議 —— 分為 phase one 和 phase two，且無論是 phase one 與 phase one、phase two 與 phase two 還是 phase one 與 phase two 之間，他們的 quorum 必須滿足節點的大多數。用數學表示的話就是要有交集：
其中， Q1表示 phase one 階段，Q2 表示 phase two 階段。這是 classic paxos 算法必須滿足的條件。論文中提及的 revision A 改進就是去掉了 phase one 之間和 phase two 之間的 quorum 交集要求，只保留了 phase one 和 phase two 兩階段之間的 quorum 保留交集要求就能達到 classic paxos 算法的效果，
在 revision A 的基礎上，論文將通過 epoch 繼續縮小 quorum 數量的範圍。Classic Paxos 算法在 phase one 階段提交提議的時候都會帶一個提案號 —— epoch，並且當前次的 epoch 要大於前一次的 epoch。為了縮小 quorum 數量範圍，論文中提出只需要保證當前次 phase one 階段的 quorum 和前一次的 phase two 階段的 quorum 有交集，即可以保證 Paxos 算法的一致性。
02 Promise Revised
Classic Paxos 在進行 phase two 階段提議前，提議者必須收到大部分 quorum 的 promises 。在論文中提及的 revision B 改進，在進行 phase two 階段提議前，也是必須滿足這樣的條件，不同的是 quorum 的範圍縮小了，只需滿足上一輪次 phase two 階段 quorum 的 promises 。讓我們考慮一下，假如一個提議者在 phase one 階段發送了一個提案號為 e 的 prepare —— prepare(e)，並且從一個接收者處收到 (e,f,v) 的 promise。此時，這個提議者就知道，如果有個提案號是 f 的提議被採納，那麼這個提議的就是 v。這時此提議者就無需再等待其他 quorum 且提案號也是 f 的 promises。因為，一個相同的提案號不可能有相同的值。此外，我們無需等待其他提案號小於 f 的 quorum 的 promises。上面，就是論文中提及的 revision C 改進。
03 Value select Revised
無論是 classic paxos 還是到目前為止改進方案，在 select value 的時候都是選擇提案號 epoch 最大的那個提議；如果最大的 epoch 的提議值是空的話，那麼提議者就可以選擇自身備選的提議。論文中提到兩種 value selection revised 方法，分別為 Epoch agnostic algorithm 和 Epoch dependent algorithm 。
先來說說 Epoch agnostic algorithm 方法。前面說過，以前的 value select 策略都是從 promises 中選擇 epoch最大的提議值，而這個策略卻完全不一樣。他用一個集合用來記錄不同 quorum 返回的 promise 是否符合待提議的要求。這些要求是他下面兩個輔助定理做為依據支撐的：
本質上嘗試逐個否定 phase two 階段中每個 quorum 元素的方式，來排除一些提議候選值。這個方法正確性的直覺是：真正被 chosen 的候選值是不會被否定掉的。
Epoch agnostic algorithm 方案只能針對 quorum，跟 epoch 完全無關的情況，Epoch dependent algorithm 方法就是加上 epoch 維度的改進版。
04 Epochs Revised
到目前為止，proposer 的 epoch 都是唯一的，相互不重疊。之所以能做到這樣，是因為第一通過了預分配機制，第二是在 phase one 階段的 vote epoch 機制。論文中提及的是第三種，就是每個 proposer 可以使用相同的 epoch 提議。怎麼做到的呢？
如果使用相同的 eooch 提議，會有三個問題。只要解決這三個問題改進的 paxos 算法就能使用。
第一，不同的 proposer 使用相同的 epoch 提議，那麼提議的值就會被 phase two 階段且沒有交集的 quorums 接收。然而，這在paxos 算法中是不允許的。怎麼解決？解決方法很簡單，那就要 phase two 階段的 quorums 有交集。
第二，被 phase two 階段某個 quorum 接收的提議可能會被相同的 epoch 的提議重寫，這樣就會導致值衝突。解決方法是隻接收提議的 epoch 大於當前已接收提議的 epoch 或是接收完全相同的提議。
第三，對於 proposers 來說，他們在 phase one 階段有可能會收到相同的 epoch 但是不同的提議(value)，這個時候 proposer 的過程就會無法進行下去。對於這種情況，論文給出的解決方法是加強 phase one 和 phase two 之間 quorums 的交集。論文中第一個問題的解決方法是要求 phase two 之間的 quorum 需要有交集，在這個問題的解決方法中，phase one 階段的 quorums 需要和這個交集也需要有交集。
總結
文章只是對論文各個改進點做了總結描述，沒有對整篇論文做深層的邏輯推理，感興趣的讀者可以下載該論文，通過論文中大量的偽代碼和交互圖自行推論。
