Byzantine Generals’ Problem

A group of generals, each commanding a portion of the Byzantine army, encircle a city. These generals wish to formulate a plan for attacking the city. In its simplest form, the generals must decide only whether to attack or retreat. Some generals may prefer to attack, while others prefer to retreat. The important thing is that every general agree on a common decision, for a halfhearted attack by a few generals would become a rout, and would be worse than either a coordinated attack or a coordinated retreat. Byzantine Generals’ Problem - WIKI

简单讲，就是所有将军需要统一行动，不可以有人攻击，有人撤退。

难点：

General cast vote for suboptimal strategy
General cast vote selectively
The messenger may fail to deliver votes
The messenger may forge false votes

Byzantine fault tolerance

Byzantine fault tolerance (BFT) is the dependability of a fault-tolerant computer system, particularly distributed computing systems, where components may fail and there is imperfect information on whether a component is failed. Byzantine fault tolerance - WIKI

BFT “拜占庭容错” 是一个分布式计算领域的容错技术。

提出者是2013年的图灵讲得主Leslie Lamport。他证明了在消息不可靠信道上传递，达到一致性是不可能的。

解法

我们做以下假设：

一致性：每个忠诚的将军必须收到相同的命令值vi（vi是第i个将军的命令）
正确性：如果第i个将军是忠诚的，那么他发送的命令和每个忠诚将军收到的vi相同。

当 n > 3m 时，即叛徒的个数 m 小于将军总数的 n 的 1/3 时，假设通信可靠，可以构造同时满足“一致性”和“正确性”的解决方法.

PBFT

BFT算法中最典型的是PBFT

Skip