2011年3月29日 星期二

[Distributed Algorithms] 第三堂: Distributed consensus with link failures

這堂課講的是 Coordinated Attack Problem,
下面是 wiki 的網頁
http://en.wikipedia.org/wiki/Two_Generals'_Problem
說明兩個將軍要攻打第三方,只有兩方合作才能打勝仗,所以需要傳令兵來互通訊息,而傳令兵傳送訊息的過程中有可能被殺 = =
所以這問題基本上是無解。



  • Deterministic Version

這問題比較學術的說法叫做 reaching consensus,
這問題要符合 Agreement、Validity、Termination,接下來會用 indistinguish 的方式證明矛盾



  • Randomized Version
randomized version 的 agreement 是將犯錯的機率控制在一個範圍內。
兩 event 不知道互相發生甚麼事情,這也是分散式系統的本質。 (consistent global snapshot)
information flow 的概念也很重要!!

沒有留言:

張貼留言