Fault Models

Nodes may crash, disconnect, or lie. Each upgrade in the fault model, from crash-stop to Byzantine, doubles the difficulty of protocol design. In engineering, "how long is too long before declaring a failure" is a trade-off with no correct answer: too short, and you falsely suspect healthy nodes; too long, and the system waits idly.

Fault Classification

Crash-Stop (Fail-Stop)

Once a node stops executing, it does not restart. This is the simplest fault model—once a node crashes, it never produces new output. Consensus protocols (Paxos/Raft) have concise proofs under this model.

Characteristics: No persistence is required (the node does not need to recover its log after a crash), and state can reside in memory. However, in practice, very few systems are truly crash-stop; most systems require crash-recovery.

Crash-Recovery

A node stops but restarts and resumes execution after an arbitrary amount of time. Recovery involves replaying the pre-crash state from persistent storage (WAL/journal). This is the most practical fault model—Raft/etcd are designed specifically for crash-recovery.

Key issue after recovery: The restarted node must prove that its log has not been lost—i.e., the log was durably written and acknowledged before the crash. This is why Raft requires fsync of log entries before replying to the leader.

Byzantine Faults

Nodes can exhibit arbitrary behavior—including sending forged messages, selectively responding, or acting maliciously. This is not limited to malicious attacks: memory bit-flips (cosmic rays), firmware bugs, or network equipment misrouting can all produce Byzantine behavior.

Byzantine faults are much harder to handle than crash faults: Paxos/Raft tolerate f crash faults with 2f+1 nodes; PBFT (Practical Byzantine Fault Tolerance) requires 3f+1 nodes to tolerate f Byzantine nodes.

Reason: Byzantine nodes can say different things to different honest nodes—honest nodes cannot distinguish between "the other party is lying" and "the network dropped the packet." The lower bound of 3f+1 for PBFT has been proven necessary.

Distribution in Practice

Real-world systems rarely require Byzantine fault tolerance—in a closed data center or cluster, crash-recovery covers the vast majority of faults. Byzantine faults mainly appear in:

• Blockchain/cryptocurrency (nodes do not trust each other)
• Cross-organizational collaboration (no common root of trust)
• Extremely critical infrastructure (Spanner uses TrueTime to prevent certain Byzantine-style clock attacks)

Network Partitions

A partition is not a crash—nodes are still running and can accept client requests, but they cannot communicate with other nodes. Partitions are the core threat to the CAP theorem: when a partition occurs, you must choose between consistency and availability.

Symmetric vs. Asymmetric Partitions

• Symmetric partition: The cluster is split into two equal parts, each containing a majority of nodes → (using Raft) only the half with the majority can elect a leader and continue serving
• Asymmetric partition: A single node is disconnected from all other nodes → it cannot become a leader and does not cause a split-brain

Split-Brain

Multi-leader systems + partition = both partitions elect their own leader → both sides accept writes simultaneously → conflicts upon partition recovery. Classic solutions:

• Raft/Paxos: Only the majority partition can have a leader (mathematical guarantee)
• System-level defense: STONITH (Shoot The Other Node In The Head) → fence the old master or even cut power directly

Timeouts

The core tension in distributed systems: timeout too short = false positive crash detection; timeout too long = slow failure detection (increasing the window of unavailability).

Raft's election timeout is a typical example: randomized between 150-300ms, ensuring different candidates have different timeouts (to avoid split votes) while being long enough to cover normal RPC latency.

Why There Is No "Correct" Timeout

Network latency is not Gaussian distributed—it has a long tail. Even if the p99 latency is 10ms, the p99.9 might jump to 100ms. If you set timeout=100ms, 0.1% of requests will be falsely timed out. If you set timeout=1s, the failure detection latency is 1s—during which the system is unavailable.

There is no theoretical solution to this problem, only engineering trade-offs. In practice: use a φ-accrual failure detector (see Chapter 05) to output a suspicion level rather than a binary decision—let the application layer decide "how much suspicion warrants a failover."

References

• Paper: "Impossibility of Distributed Consensus with One Faulty Process" (FLP, 1985)
• Paper: "Practical Byzantine Fault Tolerance" (Castro & Liskov, 1999)
• Paper: "The φ Accrual Failure Detector" (Hayashibara et al, 2004)

Keywords: crash-stop, crash-recovery, Byzantine fault, network partition, split-brain, FLP, timeout, φ-accrual