這個簡單的一致性算法的工作？

Question

爲了說服自己，像Paxos和Raft這樣的標準算法的複雜性是必要的，我們必須理解爲什麼更簡單的解決方案不能令人滿意。假設，爲了達成共識WRT事件流的N機的羣集（即執行復制的時間成長日誌），下面的算法：

1. 當一臺機器要追加消息發送到日誌，它廣播元組(msg, rnd, prev)，其中msg是消息，rnd是一個隨機數，而prev是日誌中最後一條消息的ID。

2. 當一臺機器收到一個元組時，它將msg作爲prev的子元素插入，形成一棵樹。

3. 如果一個節點有多個孩子，只有最高的那個孩子被認爲是有效的;通過樹的有效消息的路徑是主鏈。

4. 如果一條消息是主鏈的一部分，並且已經足夠大，它就被認爲是決定/最終的。

5. 如果一臺機器試圖提交一條消息，並且一段時間後它不在主鏈上，這意味着另一臺機器幾乎在同一時間廣播了一條消息，所以您重新播放它直到它在那兒。

看起來簡單，高效和靈活的崩潰。這個算法會起作用嗎？

Answer 1

我認爲你有一個問題，如果一臺機器中序號發送二元組和第一丟失（包丟失/損壞或其他）

在這種情況下，可以說，機器1已經前頁10 elemtent ID和機器2只發送（msg，rnd，10）= 11和（msg，rnd，11）= 12給機器2。在它的樹上。 機器3接收到兩者，因此將其插入主樹中。

在這個時候，你將有一個desync之間的分佈式樹木。

我建議在包裹被機器x插入樹中後發送給發件人，並等待它發送下一個包。

通過這種方式，發件人需要將以前的消息重新發送給在給定時間範圍內未能確認的機器。