起源
拜占庭位于現在土耳其的伊斯坦布爾，是東羅馬帝國的首都。由于當時拜占庭羅馬帝國國土遼闊，為了防禦目的，因此每個軍隊都分隔很遠，将軍與将軍之間隻能靠信差傳消息。在戰争的時候，拜占庭軍隊内所有将軍和副官必需達成一緻的共識，決定是否有赢的機會才去攻打敵人的陣營。但是，在軍隊内有可能存有叛徒和敵軍的間諜，左右将軍們的決定又擾亂整體軍隊的秩序。在進行共識時，結果并不代表大多數人的意見。這時候，在已知有成員謀反的情況下，其餘忠誠的将軍在不受叛徒的影響下如何達成一緻的協議，拜占庭問題就此形成。
将軍問題
拜占庭将軍問題是一個協議問題，拜占庭帝國軍隊的将軍們必須全體一緻的決定是否攻擊某一支敵軍。問題是這些将軍在地理上是分隔開來的，并且将軍中存在叛徒。叛徒可以任意行動以達到以下目标：欺騙某些将軍采取進攻行動；促成一個不是所有将軍都同意的決定，如當将軍們不希望進攻時促成進攻行動；或者迷惑某些将軍，使他們無法做出決定。如果叛徒達到了這些目的之一，則任何攻擊行動的結果都是注定要失敗的，隻有完全達成一緻的努力才能獲得勝利。
拜占庭容錯協議必須處理這些失效，并且這些協議還要滿足所要解決的問題要求的規範。這些算法通常以其彈性t作為特征，t表示算法可以應付的錯誤進程數。
很多經典算法問題隻有在t
失效
所謂拜占庭失效指一方向另一方發送消息，另一方沒有收到，發送方也無法确認消息确實丢失的情形。
在容錯的分布式計算中，拜占庭失效可以是分布式系統中算法執行過程中的任意一個錯誤。這些錯誤被統稱為“崩潰失效”和“發送與遺漏是失效”。當拜占庭失效發生時，系統可能會做出任何不可預料的反應。
這些任意的失效可以粗略地分成以下幾類：
進行算法的另一步時失效，即崩潰失效；
無法正确執行算法的一個步驟；
執行了任意一個非算法指定的步驟；
各個步驟由各進程執行，算法就是由這些進程執行的。一個錯誤的進程是在某個點出現了情況。沒有出現錯誤的進程是正确的進程。
解決算法
拜占庭問題的最初描述是：n個将軍被分隔在不同的地方，忠誠的将軍希望通過某種協議達成某個命令的一緻（比如一起進攻或者一起後退）。但其中一些背叛的将軍會通過發送錯誤的消息阻撓忠誠的将軍達成命令上的一緻。Lamport證明了在将軍總數大于3m，背叛者為m或者更少時，忠誠的将軍可以達成命令上的一緻。
為了保證上面的需求，必須滿足下面兩個條件：
1.每兩個忠誠的将軍必須收到相同的值v(i)（v(i)是第i個将軍的命令）。
2.如果第i個将軍是忠誠的，那麼他發送的命令和每個忠誠将軍收到的v(i)相同。
為了簡化以上模型，我們使用一個将軍發送命令給多個副官的形式來證明，發送命令的将軍稱為發令者，接收命令的将軍為副官，那麼上面的兩個條件可以表述為。
IC1.所有忠誠的副官遵守相同的命令。
IC2.如果發出命令的将軍是忠誠的，那麼所有忠誠的副官遵守司令（發出命令的将軍）的命令。
特别提示
：發送命令的每次隻有一個将軍，将其命令發送給n-1個副官。m代表叛國者的個數，因為将軍總數為n，所以副官總數為n-1個。IC2中副官遵守實際上是指忠誠的将軍能夠正确收到忠誠将軍的命令消息。
通過口頭消息
通過口頭消息傳遞達到一緻，如果有m個叛國将軍，則将軍們的總數必須為3m+1個以上。下面是口頭消息傳遞過程中默認的一些條件：
A1.每個被發送的消息都能夠被正确的投遞。
A2.信息接收者知道是誰發送的消息。
A3.能夠知道缺少的消息。
A1和A2假設了兩個将軍之間通信沒有幹擾，既不會有背叛者阻礙消息的發送（截斷）也不會有背叛者僞造消息的情況（僞造）。即是每個将軍都可以無誤地将自己的消息發送給其他每個将軍。（下一節中可以不需要這個必要條件）。
定義口頭消息算法OM(m)。對于所有的非負整數m，每個發令者通過OM(M)算法發送命令給n-1個副官。下面将說明OM(m)算法在最多有m個背叛者且總将軍數為3m+1或者更多的情況下可以解決拜占庭将軍問題。（考慮到網絡應用實際環境，原文使用了收到值代替收到命令。）
算法定義一個函數：majority(com1,com2,…,comn)等于多數派命令。
OM(0)算法
（1）發令者将他的命令發送給每個副官。
（2）每個副官采用他從發令者發來的命令，或者默認使用撤退命令，如果沒有收到任何命令。
OM(m)算法
（1）發令者将他的命令發送給每個副官。
（2）對于每個i，vi是每個副官i從發令者收到的命令，如果沒有收到命令則為撤退命令。副官i在OM(m-1)中作為發令者将vi發送給另外n-2個副官。
（3）對于每個i，并且jneqi，vj是副官i從第（2）步中的副官j發送過來的命令（使用OM(m-1)算法），如果沒有收到第（2）步中的副官j的命令則默認為撤退命令。最後副官i使用majority(v1,…,vn-1)得到命令。
接下來實際的考慮一個n=4，m=1的情況：
1.當副官3是背叛者，以副官2為例
第一步發令者執行算法OM(1)将自己的命令發送給三個副官，三個副官都正确地收到了命令。
第二步每個收到命令的副官都作為發令者執行算法OM(0)，将自己的命令轉發給其餘副官，因為副官3是背叛者，所以他給副官2傳遞的消息會是假消息。副官2最後根據majority函數來決定命令。
這樣背叛的副官3同理也幹擾不了忠誠的副官1和發令者的決定。下面看看如果發令者是背叛者。
2.發令者是背叛者，其餘副官為忠誠的
第一步
：發令者向副官發送了不同的命令，實際情況中是一個攻擊者向不同方發送了不同的值進行欺騙。
第二步
：副官收到命令後，搖身一變為發令者執行OM(0)向所有的副官發送命令，這樣所有副官的到命令會都相同
，這樣所有命令都達不到大部分。
文章接着就證明了OM(m)算法對任意m都是可以滿足，首先引入一個引理（歸納法證明）：
引理1：
對于任意m和k，如果有超過2k+m個将軍和最多k個背叛者，那麼算法OM(m)滿足IC2（回顧下IC2指的是，如果将軍是忠誠的，所有的副官遵守将軍命令）。
證明
：當m=0的時候，OM(0)在将軍是忠誠的時候滿足IC2。當m>0時，首先将軍将命令傳遞給n-1個副官，然後每個副官對n-1個将軍執行OM(m-1)算法。因為假設了n>2k+m（引理中有将軍數大于2k+m），所以n-1>2k+(m-1)>=2k（即每一輪中副官總數不小于背叛者的兩倍），這樣每輪OM(m-k)算法中忠誠的副官收到的命令都是majority(v1,v2,...,v(n-1))，其中忠誠副官發送的命令大于或者等于一半。
接着解決拜占庭将軍問題。
定理1：對于任意m，如果有超過3m個将軍和最多m背叛者，算法OM(m)滿足條件IC1和條件IC2。
證明：通過m的歸納法證明，我們通過假設OM(m-1)成立來證明OM(m)m>0。首先考慮發送命令的将軍是忠誠的。那麼将引理中k設為m則OM(m)滿足IC2，IC1在發令将軍是忠誠的情況下也滿足。
接着考慮m個背叛者中有一個是發令者，那最多就隻有m-1個副官是背叛者了，又因為有3m個将軍，所以副官的總數超過3m-1，且有3m-1>3(m-1)。因此通過歸納法假設OM(m-1)滿足IC1和IC2（最多3(m-1)個将軍和最多m-1個背叛者）。那麼任意兩個忠誠的副官j在OM(m-1)獲得相同命令vj，那麼在OM(m)算法中每個忠誠的副官都會收到(v1,v2,...,v(n-1))，可知滿足條件IC1和IC2。
通過簽名消息
簽名消息在除了滿足口頭消息A1-A3三點要求外還應該滿足下面A4：
A4（a）簽名不可被僞造，一旦被篡改即可發現。
（b）任何人都可以驗證将軍簽名的可靠性。
下面定義一個類似于上面majority函數的choice來決定副官的選擇：1.當集合V隻包含了一個元素v，那麼choice(V)=v；2.choice(o)=RETREAT。
初始化Vi=空集合
（1）将軍簽署命令并發給每個副官。
（2）對于每個副官i。
（A）如果副官i從發令者收到v:0的消息，且還沒有收到其他命令序列，那麼。
（i）使Vi為{v}。
（ii）發送v:0:i給其他所有副官。
（B）如果副官i收到消息v:0:j1:...:jk且v不在集合Vi中則。
（i）添加v到Vi。
（ii）如果k。
（3）對于每個副官i，當不再收到消息，則遵守命令choive(Vi)。
算法的幾點說明：
算法第三步并沒有說明副官如何判斷沒有新的消息，可以通過兩個解決方法：一是要求每個副官收到消息後要麼簽名轉發該消息，要麼發送一個通知他将不發送這個消息；二是設置一個超時時間，如果在該時間段還沒有收到消息，則認為不再收到消息。
算法SM(m)中，讓副官簽名是确認其收到了該消息（有點像來了份文件給每個領導批閱）。在SM(1)中副官收到消息就不用簽字了，因為不用轉發給其他副官。
定理2
：對于任意m，最多隻有m個背叛者情況下，算法SM(m)解決拜占庭将軍問題。
Proof：首先證明IC2，如果發令者是忠誠的，那麼所有的副官一定收到相同的命令，因為簽名無法篡改，且IC1也就滿足了。證明IC1隻用考慮發令者是背叛者的情況（重新回顧下IC1是指所有忠誠的副官執行相同的命令），IC1要求兩個忠誠的副官（i，j）必須收到相同的命令集合Vi、Vj，也就是Vi中每個v都在Vj中。會存在兩種情況，其一當副官i收到v令的序列後，加入到Vi，并将其發送給副官j，j将命令v保存；其二副官i收到命令v:0:j1:...:jk:i，其中有jr=j，所以由A4可知副官j也收到了該命令。
k
k=m。發令者是背叛者，最多隻有m-1個副官是背叛者。因此，最少有一個序列j1,...,jm是忠誠的。那麼j一定收到這個忠誠的副官序列發來的值v所以副官j收到v。
