Byzantine generals; recovery technique

Byzantine generals problem

The Byzantine generals problem (Lamport, Shostak, Pease) models agreement in a system where some processes may be faulty and send wrong or conflicting messages (Byzantine failure: a process behaves arbitrarily, even maliciously).

Several divisions of the Byzantine army surround a city, each commanded by a general. They must agree on a common plan (attack or retreat) by sending messages, but some generals are traitors who may tell different generals different things. Required: (1) all loyal generals decide on the same plan; (2) a small number of traitors cannot cause loyal generals to adopt a bad plan.

Result: with m faulty processes, agreement is possible only if the total number of processes is n ≥ 3m + 1, i.e. more than two-thirds are loyal. With 3 generals and 1 traitor, agreement is impossible.

Example with n = 4, m = 1 (general 3 is faulty):

1. Each general sends its value to all others: G1 sends 1, G2 sends 2, G3 sends 3 (faulty may send anything), G4 sends 4.
2. Each general collects the received values as a vector. For example, G1 has (1, 2, x, 4).
3. Each general sends its vector to all others. The faulty G3 sends arbitrary vectors.
4. Each general examines the i-th element of all vectors received and takes the majority; if no majority, the value is UNKNOWN.

G1 gets: (1,2,y,4) (a,b,c,d) (1,2,z,4) from G2,G3,G4
Majority per position -> (1, 2, UNKNOWN, 4)
G2 and G4 reach the same result.

All loyal generals end with the same vector, and the entries for loyal processes are correct. So the loyal ones agree, even though G3's value is unknown.

What we learn: Byzantine faults are the hardest to tolerate; agreement needs 3m+1 processes and several rounds of messages (m+1 rounds), so it is costly. It is used where failures can be arbitrary (aircraft control, critical systems).

Failure recovery technique: checkpointing (backward recovery)

After a failure, the system restores a previously saved consistent state and continues.

1. Each process saves its state (a checkpoint) on stable storage.
2. In coordinated checkpointing, a coordinator asks all processes to take tentative checkpoints, then makes them permanent, giving a consistent global state (no orphan messages).
3. When a process fails, all processes roll back to the latest checkpoint (the recovery line), and execution restarts. Logged messages can be replayed to recover the work done after the checkpoint.

Its limit is the lost work since the last checkpoint and the cost of saving; it does not handle Byzantine (arbitrary) faults, which need voting and agreement.