Byzantine Generals

Question 1

What is the Byzantine Generals problem?
(Definition)

Answer 1

A game theory problem that illustrates the challenges of reaching consensus in decentralised systems, especially when some participants may be malicious.

Question 2

What is the back-story behind it?
(4 points) (S.E.T.S) (NOTE)

Answer 2

1. Several divisions of the Byzantine Army are comaped outside an emeny city.
2. Each general votes to either attack, or retreat.
3. The generals must agree on a consensus plan of action:
4. Some generals may be traitors, trying to prevent a consensus being reached.

NOTE: The same decision is taken by all loyal generals.

OPTIONAL LONG NOTE: Imagine several divisions of the Byzantine army camped outside a city. Each division is led by its own general. These generals must agree on a common battle plan — either attack or retreat. But there’s a catch:

• Some generals might be traitors trying to sabotage the plan.
• The loyal generals need to reach agreement, even if some messages are false, lost, or delayed.

The problem is to devise a communication strategy such that:

1. All loyal generals agree on the same plan.
2. If all loyal generals decide to attack (or retreat), they actually do so.

Question 3

What is the problem definition? (Algorithm) (A.A)

Answer 3

Note: Never really stated.

There must exist an algorithm which ensures that:
1. All loyal generals decide upon the same plan of action.
2. A small number of traitors cannot imply a bad plan. (stricly less than one-third)

Question 4

What is meant by “traitor”?

Answer 4

Traitor implies a deliberate attempt to cause distributed failure or a faulty machine/node causing undefined behaviour.

Question 5

What do the conditions represent?

Answer 5

Conditions 1 and 2 of the paper are the requirements for correct overall system behaviour.

Question 6

What is IC defintion and problem? (Condition 1 and Condition 2 or the Byzantine Fault tolerant protocol)

Answer 6

IC is interactive consistency.
problem defintion: A commanding general must send an order to his n-1 lietenant generals such that:
IC1: All loyal lietenants obey the same order.
- Ensures consistency among participants
IC2: If the commanding general is loyal, then every loyal lietenant obeys the order he sends.
- Ensures correctness (functions as intended)

Simplified:
- If the commander is honest then all honest generals agree with him (IC2) hence they all agree on the same plan (IC1)
- If the commander is dishonest then IC2 may not apply but IC1 must still be preserved, all loyal generals must agree, even if on a wrong value.

Question 7

What is the 3 generals impossibility? 2 Reasons why?
Explain with 2 cases?

Answer 7

Definition: NO solution exists for three generals that works in the presence of a single traitor. Mathematically impossible.

Reasons why it is impossible:
- If a faulty commander can send different messages to each loyal general, the honest generals cannot:
1. detect the inconsistency
2. tell if the commander or a lietenant is lying/traitor.

Example 1:
Generals: A (Commander), B and C
A is the traitor.
A sends “attack” to B and “retreat” to C.
B and C receive conflicting orders.
B and C cannot tell if either A is lying or the other lieutenant is.

Example 2:
Generals: A (Commander), B and C
C is the traitor.
A sends “attack” to B and “attack” to C.
C tells B to retreat.
B cannot tell if the commander is lying or B is lying.

Question 8

What is the OM Algorithm (Oral Messages)?
(Defintion, Assumptions made, Process ‘recursive, 4 points’)

Answer 8

Defintion: Outlines how consensus can be achieved using the OM Algorithm.

Assumptions:
1. Every message that is sent is delievered correctly
2. The receiver of a message knows who sent it.
3. The absence of a message can be detected.

A1 and A2 prevent a traitor from interfering with the loyal generals communication. A3 prevents a traitor who tries to prevent a decision by simply not sending messages.

OM(m) - The Recursive Algorithm - Process
OM(m) is the algorithm to tolerate up to m Byzantine faults.

Base Case: OM(0)
- The commander sends a value to each lietanant.
- Each lieutenant uses the value he receives from the commander, or uses the value RETREAT if he receives no value.

Recursive Case: OM(m), m>0
- The commander sends his value (v) to every lietanant.
- Each lietanant:
* Treats the received value as a new command, and
* Runs OM(m-1) as if it were now the commander.
* Sends this value to the other n - 2 lieutenants.
- Each lieutenant receives values from the others, forming a list of received values.
- Each lieutenant uses a majority function to decide the final value based on the values received.

Question 9

Give 2 examples of the OM algorithm in action?

Answer 9

Example 1:
1. Commander A sends order to B, C, D OM(1)
A → B: “Attack”
A → C: “Attack”
A → D: “Attack”
(NOTE: If A were a traitor, it could send different orders to each.)

2. Each lieutenant now acts like a “commander” in OM(0)
   They take what they received from A, and forward it to the other lieutenants:

B → C: “Attack” (what B received from A)
B → D: “Attack”
C → B: “Attack”
C → D: “Attack”
D → B: “Attack”
D → C: “Attack”

3. Each lieutenant now has 3 messages:
   Let’s look at Lieutenant B:

From A (original): “Attack”
From C: “Attack”
From D: “Attack”
So B’s list is: [Attack, Attack, Attack] → majority is Attack.

Same goes for C and D.
✅ Final Decision:
Each loyal lieutenant takes the majority of the values received.
Since all received “Attack” → they all agree: Attack.

Example 2:
Assume C is the traitor, and lies to D.
A sends “Attack” to B, C, D.
C sends a fake message to D: “Retreat” (instead of “Attack”).

Now D sees:

From A: “Attack”
From B: “Attack”
From C: “Retreat”

List = [Attack, Attack, Retreat] → Majority = Attack
Even with one lie, the majority holds.
✅ Still reaches consensus!