Paxos領導人選舉可能不會終止

Question

我正在研究Paxos做了簡單的論文，而且我很困惑Paxos不保證進度，如果有兩位提案人以較高的提案數量彼此競爭，並且正如文章中所建議的那樣，爲了保證進步，必須選出一位傑出的提案人，使他成爲領導者。

但是，隨着人們建議使用Paxos來選出傑出的提議者，這又出現了問題，這又要求領導者保證進展。

我知道給出的場景可能是一個特定的實現，例如，如果給予進程選擇的區別集是有序的，我的意思是P1集< P2集。

但我想在實際的實現中理解這是如何處理的？

Answer 1

通常的做法是簡單地使用隨機超時，其中有一個可能的延長領導決鬥的可能性較低。如果您在紙上搜索「超時」，那麼它會提到這一點。

如果一個穩定的領導者平均需要X秒才能出現並取得進展（我們可以使用最小的消息往返次數來估計），那麼我們可以簡單地讓每個節點在某個時間間隔內隨機超時X的倍數。通過在每次嘗試成爲領導者時使用新的隨機數，我們具有擴展領導者決鬥的低概率。

如果我們將X的倍數設置爲隨機超時的上限，則我們有較低的擴展領導決鬥概率。然而，在領導者出現之前，我們的平均時間也更長。所以這是一個折衷。

如果實現需要非常快速的故障轉移，我們可以使用低超時隨機時間間隔，但嘗試實現領導者對決快速解決的機制。你可以發明任何機制。

確保一個節點具有成爲領導者優勢的簡單機制如下。每個節點都有一個唯一的號碼用來排列它的選票。在領導決鬥期間，每個節點都可以使用指數回退，該回退由自己的唯一編號進行縮放。例如，如果在每次失敗嘗試成爲領導者時節點編號爲N，那麼我們可以將其超時窗口的上限乘以1 + 1/N。這意味着，在任何決鬥期間，具有最高N的節點在嘗試成爲領導者時會更積極，因爲其他節點將更快地退避。