The Byzantine Generals Problem

L. Lamport, R. Shostak, and M. Pease @ SRI International

ACM Transactions on Programming Languages and Systems, July 1982, pages 382-401

Byzantine Generals Problem and its Applications

Byzantine General Problem

The Classic Problem
Each division of Byzantine army are directed its own general
Generals, some of which are traitors, communicate each other by messengers
Requirements:
All loyal generals decide upon the same plan of action
A small number of traitors cannot cause the loyal generals to adopt a bad plan
The problem can be restated as:
All loyal generals receive the same information upon which they will somehow get to the same decision
The information sent by a loyal general should be used by all the other loyal generals
The above problem can be reduced into a series of one commanding general and multiple lieutenants problem - Byzantine Generals Problem :
All loyal lieutenants obey the same order
If the commanding general is loyal, then every loyal lieutenant obeys the order she sends

Reliability by Majority Voting

One way to achieve reliability is to have multiple replica of system (or component) and take the majority voting among them
In order for the majority voting to yield a reliable system, the following two conditions should be satisfied:
All non-faulty components must use the same input value
If the input unit is non-faulty, then all non-faulty components use the value it provides as input

Impossibility Results

No solution exists if less than or equal to 2/3 generals are loyal

A Solution with Oral Messages - No Signature

Oral Message Requirements and their Implications

A1 - Every message that is sent is delivered correctly
The failure of communication medium connecting two components is indistinguishable from component failure
Line failure just adds one more traitor component
A2 - The receiver of a message knows who sent it
No switched network is allowed
The later requirement -- A4 nullifies this constraint
A3 - The absence of a message can be detected
Timeout mechanism is needed

Solution

If less than 1/3 generals are traitors, this problem can be solved
Algorithm - recursive
Lieutenants recursively forward orders to all the other lieutenants
Commander's order = majority (v(c), v(1), v(2), ..., v(n))
v(i) = majority (v(i), v(i)(2), v(i)(3), ..., v(i)(n)), 1<= i <= n
v(i)(j) = majority (v(i)(j), v(i)(j)(3), v(i)(j)(4), ...)
...

A Solution with Signed Messages

Additional Requirements and their Implications

A4:
A loyal general's signature cannot be forged
Anyone can verify the authenticity of a general's signature
Implication
Digital signature is required

Solution

If at least two generals are loyal, this problem can be solved
Algorithm - recursive
Lieutenants recursively augment orders with their signature and forward them to all the other lieutenants
Each lieutenant maintains a set of orders she has received, i.e., the possible sets are:
{ attack },
{ wait }, or
{ attack, wait }
Lieutenant takes action according to the value of the set
{ attack, wait } means the commander is a traitor

Missing Communication Paths

Network topology or policy could keep a general sending/receiving messages to/from another general

This constraint makes Byzantine problem more general

Oral Message

If the communication graph is 3m-regular and less than or equal to m generals are traitors, this problem can be solved
k regular set of neighbors of a node p
the set of all neighbors of p, whose size is k
for any node not in the set, there exists a disjoint path, not passing through the node p, from a node in the set
k regular graph - every node has k regular set of neighbors
Algorithm - extension of oral message
Lieutenants recursively forward orders to all its k regular neighbors
Commander's order = majority (v(c), v(1), v(2), ..., v(n))
v(i) = majority (v(i), v(i)(2), v(i)(3), ..., v(i)(n)), 1<= i <= n
v(i)(j) = majority (v(i)(j), v(i)(j)(3), v(i)(j)(4), ...)
...

Signed Message

If the subgraph of loyal generals is connected, this problem can be solved