# 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