背景
高可靠的分布式系统中需要有较高的容错能力，包括处理其中一部分组件和其他组件返回的消息互相冲突的场景。这个问题可以类比于拜占庭军队围攻一个城池时，各个将军间只能通过信使通信，而将军中可能会有叛徒传递错误的消息。因此需要一种算法能够保证忠诚的将军可以互相达成一致。
假设拜占庭将军们在敌军的周围，将军之间的通信只能通过信使，每个将军根据自己观察的敌情确定下一步的军事行动。将军中可能有背叛者来阻止忠诚的将军达成一致。为了保证下一步军事行动的一致性，将军们需要
- 忠诚的将军最终的决定是一致的。（背叛者可以按照自己的意愿做决定）
- 少数的背叛者不能导致忠诚的将军做出错误的决定。
将军i对外发出的消息是v(i)，该消息可以理解为将军i对某一行动的观点，比如是否要攻击。
求解算法
假如每个将军获取的信息一致，则采用大多数人同意的方案为最终方案即可满足条件1和条件2。但是背叛者可能给其他将军发的消息是不一样的，在这种场景下，为了满足上述条件：
- 每个忠诚的将军获取相同的消息，也就是说忠诚的将军要有选择地接受消息。
- 如果i将军是忠诚的，则该将军发的消息v(i)必须被其他忠诚的将军接受。
以单个将军为研究对象，则上述两个条件可以等价于
拜占庭将军问题 一个指挥官给他的n-1个副官下达命令的方式必须满足：
使用OM(m)代表在n个将军中有m个背叛者的口头信息算法（oral message algorithm），majority函数表示从v1,…,vn-1中取取值的算法，经典的majority函数是取集合中的大多数为最终结果。口头信息算法可以如下表示
OM(0)
- 指挥官将自己的值发送给各个副官
- 每个副官使用从将军那获取的值作为自己的结果
OM(m), m>0
- 指挥官将自己的值发送给各个副官
- 对于每个副官i，vi是从指挥官那里获取的值。然后该副官再作为将军按照OM(m-1)的算法发送给其他n-2个副官。
- 对于每个副官j，vj是从副官j那里获取的值，然后使用majority函数从获取的值的集合中选取一个值作为自己的值。
经证明当n大于3m的时候OM(m)能够满足一致性。
首先对于m=1, n=4的场景。假如指挥官是忠诚的，则对于每个副官而言，收到的值的集合为{x, x, y}，因此根据majority函数可以确定x作为最终的值。如果指挥官是背叛者，则每个副官收到的集合为{x, y, z}则每个副官做出的决定依然是相同的。因此在这两种情况下，忠诚的副官们都能做出一致的决策。
下面使用归纳法证明对于m>0的场景下OM(m)都是成立的。假如指挥官是忠诚的，则各个副官通过从将军以及其他副官处收到的消息，可以很容易通过majority函数觉得最终结果。假如将军是背叛者，则剩下的n-1个指挥官中就有m-1个背叛者，因为n>3m，所以n-1>3m-1>3(m-1)，因此所有副官满足OM(m-1)的条件，即可满足一致性。
而当n小于等于3m时，以n=3, m=1为例，对于副官1而言，无法区分这两种情况，因此无法保证当指挥官是忠诚的时候，忠诚的副官要执行将军的命令，因此这种情况是不满足拜占庭将军问题的条件的。
带签名的口头信息算法
带签名的口头消息算法指的是在口头消息的条件上加一个条件
- 忠诚的将军的签名不能被修改，对忠诚的将军的发出的消息的修改能够被检测到
- 任何人都能够校验将军的签名
而对于背叛者的签名没有特别的要求。
choice函数被定义为从一个指令集中获取一个值的函数，同时需要满足两个条件
- 如果指令集V只含有一个元素v，则choice(V)=v
- 空指令集的choice为默认值。
v:i表示将军i签名的值v，v:i:j表示将军j签名的值v:i。对应的带签名的口头信息算法SM(m)为
- 初始化Vi为空集
- 指挥官给各个副官发送签过名的值。
- 对于副官i，如果收到的消息是v:0（0代表指挥官），并且还没有收到其他消息的时候，他将Vi={v}，同时发送v:0:i给其他副官；如果收到的消息是v:0:j1:…:jk，并且v不在Vi中，则将v添加到Vi中，如果k
- 对于副官i，当其不再接收到消息的时候，使用choice函数从集合中选一个值作为最后结果。对于不再接受到消息的判断条件可以是超时也可以是其他方式。
可以证明只要n>m+1即可获得拜占庭将军问题的解。
高可靠系统
在高可靠系统中，通常会使用多个处理器计算同一个问题，然后使用结果中的大多数来作为最终结果。这样做是基于每个处理器都是不会算错的，在相同的输入中每个处理器都能得到相同的结果。总结起来如下
- 所有正确的处理器必须使用同样的输入
- 如果输入单元是正确的，所有正确的处理器必须使用其结果作为自己的输入。
这与拜占庭将军问题的两个条件相同。