跳到主要内容

Unreliable Failure Detectors for Reliable Distributed Systems

TL;DR​

  • Consensus 和 Atomic broadcast是 equivalent的，能解 consensus的演算法，就可以解 atomic broadcast
  • 要在 asynchronous的環境解決 consensus，至少需要 weak accuracy的failure detector
  • 要在 asynchronous環境解決 BGP問題，至少需要strong accuracy的failure detector
  • 因為FLP Theorem已經證明了無解，所以以上現實中不存在weak accuracy failure detector和strong accuracy failure detector
  • 現實系統還是能用asynchronous架構，因為我們不需要weak accuracy永遠滿足，只需要足夠長的時間滿足，就可以應用此理論來設計系統

Note 因為這篇論文內容非常的多，這篇只會放名詞定義跟結論，重要的證明會放在 Unreliable Failure Detectors for Reliable Distributed Systems (證明篇)

Introduction​

藉由引入failure detector和failure pattern，我們就可以說某個asynchoronous algorithm能不能用此failure detector和failure pattern來解決某個分散式系統問題。反過來，我們也可以說需要多強的failure detector才可以在某個failure pattern條件下，解決某個分散式系統問題。

對應標題的unreliable，failure detector的結果可能會出錯，即使failure detector的結果出錯，也不應該影響此演算法的行為。例如解決consensus的演算法，即使所有的detector都誤認為process pp fail了，也不應該影響pp參與決策並且達成共識。

Failure Detector​

Detector擁有兩個properties:

  • Completeness
  • Accuracy

Completeness​

Strong Completeness: Eventaully 每個 faulty process，都存在"每個"detector的error list裡面。

Weak Completeness: Eventaully 至少有一個detector 辨識出所有的faulty processs。

單純只看 completeness是沒有意義的，假設某個detector把所有的process，不管是correct 或是 faulty都送進 error list裡面，它也滿足 strong completeness，但此detector是沒有用處的。

Accuracy​

Accuracy 分成四個屬性：

Strong Accuracy: 所有fault process在crash之前，沒有被suspect。

Weak Accuracy: 至少有一個correct process在crash之前，從來沒被誤判成faulty process。

Eventual Strong Accuracy: Eventually (在某個時間點 tt以後)，所有的correct process都沒被誤判成faulty process。

Eventual Weak Accuracy: Eventually (在某個時間點 tt以後)，至少有一個correct process 沒被誤判成faulty process。

Failure Detector Classes​

Completeness和Accuracy總共有8種組合 (2x4)，但我們可以證明Weak Completeness detector 可以reduce成 Strong Completeness dector，所以任合需要Strong Completeness dector的演算法，都可以使用Weak Completeness detector來處理，因此實際上只有4種組合。

Reliable Broadcast​

我們定義 Reliable Broadcast 保證:

  • 所有的correct process 都deliver 同樣的message set
  • 所有correct process的message都delivered
  • Spurious message不會被deliver

Reliable Broadcast提供兩個operation：R-broadcast和R-deliver。

Solving Consesus using Unreliable Failure Detectors

  • 如果failure detector擁有weak accuracy，要解決Consensus問題，可以允許任何數目的node failure
  • 如果failure detector擁有eventual weak accuracy，至少需要majority的correct process才能處理consensus
  • eventual strong detector也無法在沒有majority的情況下解決consensus

Atomic Broadcast​

定義​

  • Total order: 所有的process都有同樣順序的deliver順序

Conclusion​

  • Atomic Broadcast跟consensus等價
  • 可以solve consensus的演算法就可以solve Atomic Broadcast

Comparing Failure Detector Classes​

image info image info

Conslusion​

  • 拜占庭問題只能用strong accurcy來解(在asynchronous system)
  • Clock synchronization只能用synchronous system來解

References​