Dependability, K-fault, Byzantine

Dependability requirements

A fault tolerant system must be dependable, which covers:

• Availability: the system is ready to be used immediately; it is the probability that the system works correctly at a given instant.
• Reliability: the system runs continuously without failure over a time interval (high MTTF).
• Safety: when the system fails, nothing catastrophic happens.
• Maintainability: how easily a failed system can be repaired. (Often security, i.e. confidentiality and integrity, is also included.)

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 are enough: 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.

Agreement in a faulty system

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 the 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 (but, being faulty, may send anything), G4 sends 4.
2. Each general collects the received values into 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 the vectors it received and takes the majority; if there is 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 the loyal processes are correct. So the loyal generals 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. Byzantine agreement is used where failures can be arbitrary (aircraft control, other critical systems).