Byzantine generals; K-fault principle

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).

Basic principle of K-fault tolerance

A system is K-fault tolerant if it can continue to provide correct service despite the failure of up to K components.

Basic principle (redundancy): replicate the components so that failures are masked.

• If processes fail silently (fail-stop/crash), K+1 replicas suffice: if K fail, at least one still works and gives the answer.
• If processes fail arbitrarily (Byzantine), and the group takes a majority vote, at least 2K+1 replicas are needed so that the K+1 correct ones outvote the K faulty ones. For agreement among Byzantine processes, 3K+1 are needed.

Example: a group of 5 servers with majority voting tolerates K = 2 arbitrary failures; with crash failures only, K+1 = 3 servers tolerate 2 crashes.