paxos - 有人可以解釋接受郵件的例子

Question

我在Paxos paxos value choice 上看過這篇文章，但我仍然不清楚。假設我們第一次運行Paxos，Proposer發送Prepare和Acceptors答覆（null，null），因爲他們沒有學到任何價值，所以Proposer同意自己的價值並將其發送給他們接受的接受者。當投保人收到了無極-ACK和需要發送接受消息這是困惑我的事情是：如果有任何接受者此前接受任何建議

，那麼他們就會已將它們的值投保人他現在必須將其提案的價值設置爲與接受方報告的最高提案數相關的價值。 （維基百科）

我不明白這個—什麼是選擇的重要意義「它與接受者報道的最高提議號相關聯的價值呢？」有人能用一個例子來解釋這個嗎？

Answer 1

在許多分佈式協議和無鎖/無等待算法中，演員將完成另一個演員未完成的工作。 Paxos的提議者將盡可能完成其他提議者的工作。 （這不是關於如何使其他提議者發揮作用）。如果原提議者或某些接受者在算法過程中不可用，這一點非常重要。

例如，原提議者（Paul）發出他的準備和接受，但在將接受發送給其中一個接受者（藝術）之前死亡。大多數接受者已經接受了價值（A），因此選擇了價值，但是整個系統可能對此一無所知。另外一位提議者佩吉來了。她發出了自己的建議，並從亞當那裏得知價值A已被某人接受。請注意，它可能也可能不是多數。爲了安全起見，她將A退出，現在Art學習價值。

Paul   Alice Adam Art   Peggy 
|-propose(1)--->|---->|--->| 
|<----ack(_,_)--|-----|----| 
|-accept(A,1)-->|---->| X    + 
X    |<----|<---|<---propose(2)-| 
       X  |------ack(A,1)----->| 
          |-ack(_,_)----->| 
       |<----|<---|<--accept(A,2)-| 
       |-----|----|-ack---------->| 

你可以看到，至少有兩件事情發生在這裏：在準備階段，佩吉學會了接受值;在接受階段，她將選定值傳播給接受者的其餘部分。

不需要像大多數接受者那樣接受該值，如上例所示。但佩吉在發送她的接受消息之前只需等待大部分準備工作。這是因爲所接受的答案的簡單多數將始終包含所選值。

（請注意，如果佩吉沒有不送出價值A，她將不得不改變所選擇的答案，違反了共識不變。）

讓我們在多個值由返回另一個例子準備確認：（A，1）和（B，2）。我們可以從這種情況下做出一些扣除。

1. 的存在（B，2）是指大多數接受器都ack'd一個準備（2）消息，從而
2. 它是不可能是A已經被選擇（但不是不可能），因爲大多數接受者將拒絕接受（A，1）消息。
3. （B，2）的存在也意味着它是可能的 B已被大多數受體選擇。提議者在收到答覆之前不會知道。

---

更新：在回答評論的一些問題。

客戶端在這一切中扮演什麼角色？

這取決於應用。我維護的Paxos應用程序由兩種外部事件驅動：時間和客戶端寫入請求。客戶端請求寫入數據庫;服務器使用Paxos來複制並同意寫入;然後將結果發送回客戶端。 我的應用程序中的客戶端根本不瞭解Paxos，並且不參與協議。

在其他應用程序中，客戶端可擔當提議者的角色。

爲什麼Peggy在準備階段後沒有使用她自己的價值？

首先，請注意，Peggy只等待接受者的簡單多數[ceil(N/2)]作出迴應。這意味着Peggy不知道受體的結果。這個數字是，比簡單多數小1。

如果Peggy從Prepare階段收到一個值，她必須假定其他主機也具有該值。這將通過簡單多數的門檻，這意味着該值可能已被多數人選中。如果佩吉是使用她自己的價值應該可以（有時會）違反了一致的不變，一旦選擇一個值，總是選擇相同的值。

爲什麼佩吉使用由準備階段返回最高值相關聯的價值？

對此的回答就在更新的正上方，她認爲Prepare階段返回多個值。基本上，她認爲最高的回報價值已被大多數接受者接受;而且大多數接受者會以較低的round-id（他們將會）拒絕任何價值。