Skip to main content

Fault tolerance; Byzantine failure

Short answer

A fault tolerant system continues correct service despite component failures using redundancy. Byzantine failure is an arbitrary failure where a process may produce wrong or malicious responses. The Byzantine generals problem illustrates agreement: with n≥3m+1 processes (m traitors), loyal generals exchange and compare vectors in multiple rounds, taking majority to reach a common decision.

What do you mean by fault tolerant system? What do you mean by Byzantine Failure? Explain Byzantine Generals problem to illustrate how agreement can be reached in faulty system.

Fault tolerant system

A fault tolerant system continues to provide correct service even when faults occur in its components. It does so by redundancy (information, time and physical) and by detecting, masking and recovering from faults.

Byzantine failure

A Byzantine failure (arbitrary failure) is a failure in which a process behaves in an arbitrary way: it may produce wrong results, send different values to different processes, or even act maliciously, and it may do so without being detected. It is the hardest class of failure.

Agreement through the 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).

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Distributed System chapter 9 questions →