容錯拜占庭

拜占庭問題與兩軍問題

瞭解過比特幣和區塊鏈的人,多少都聽說過拜占庭將軍問題,或聽說過比特幣(或區塊鏈)的一個重要成就正是解決了拜占庭將軍問題。但真正明白這個問題的人並不多,甚至知道這個問題實質的人都很罕見。本文是一篇技術科普,將重點提供了拜占庭將軍問題本身對本質及經典演算法的解析,並探討與之相關的一些問題。筆者參考了不少 […]

拜占庭將軍問題。口頭演算法OM(n.m);n=3m 1

一、拜占庭問題的背景這裡就不再介紹直接說演算法: 下面的這個截圖是從Lamport發表的論文中擷取的: 對於這個演算法需要說明的是: (1) 在第一輪 將軍會把訊息傳送給所有的副官,第i個副官收到的記為 Vi。如 1(這裡代表的是Attack) (2) 在第二輪裡面,Li(即第i個副官)會懷疑將軍發 […]

拜占庭將軍問題見解

二、拜占庭容錯機制         拜占庭將軍問題(Byzantine failures)點對點通訊中的基本問題,含義是在存在訊息丟失的不可靠通道上試圖通過訊息傳遞的方式達到一致性是不可能的。拜占庭假設是對現實世界的模型化,由於硬體錯誤、網路擁塞或者斷開以及遭到惡意攻擊,計算機和網路可能出現不可預料 […]

拜占庭將軍問題深入探討

瞭解過比特幣和區塊鏈的人,多少都聽說過拜占庭將軍問題,或聽說過比特幣(或區塊鏈)的一個重要成就正是解決了拜占庭將軍問題。但真正明白這個問題的人並不多,甚至知道這個問題實質的人都很罕見。本文是一篇技術科普,將重點提供了拜占庭將軍問題本身對本質及經典演算法的解析,並探討與之相關的一些問題。筆者參考了不少 […]

拜占庭將軍問題(二)——口頭協議

在上一篇文章中,介紹了拜占庭將軍問題的描述、條件和結論。在傳輸口頭訊息(Oral Messages)時,少於3m 1個將軍中有m個叛徒時,拜占庭將軍問題是無解的。Leslie在原文1中, 提出了一種傳輸口頭訊息時拜占庭將軍問題的一種解法。 定義 首先,為定義口頭訊息,拜占庭將軍訊息系統具有以下假設: […]