Failing gracefully

Faults, errors, failures

Dependability research separates three links in a chain. A fault is the cause: a cosmic ray flips a bit, a cable is cut, a programmer writes a bug. An error is the resulting incorrect internal state. A failure happens when that error reaches the service boundary and users see wrong or missing behavior. Fault tolerance breaks the chain before the failure.

Every technique on this page uses one of three kinds of redundancy. Information redundancy adds extra bits, as in checksums and error-correcting codes. Time redundancy repeats the work, as in retries and transactions that re-execute. Physical redundancy adds extra hardware or processes, as in replicas and spare servers.

PaperAvižienis, Laprie, Randell & Landwehr, "Basic Concepts and Taxonomy of Dependable and Secure Computing," IEEE TDSC 1(1), 2004

Measuring availability

Availability is the fraction of time a service works: A = MTTF / (MTTF + MTTR), where MTTF is mean time to failure and MTTR is mean time to repair. Shortening repair time improves availability as much as making failures rarer, and it is often far cheaper.

How components are connected changes the result dramatically:

ReadGoogle SRE book, "Embracing Risk"

Failure models

A fault-tolerance mechanism is only correct relative to the failures it assumes. Stronger assumptions make protocols cheaper; weaker ones make them more robust.

Why majorities? With 2k + 1 replicas, any two majorities share at least one member, so a decision made by one majority can't be contradicted by another, even after k replicas fail. Byzantine nodes can lie, so the honest nodes in two quorums must overlap by more than k. That requires 3k + 1.

Networks have failure models too. A synchronous model bounds message delay and processing time. An asynchronous model bounds nothing, and in it no deterministic protocol can guarantee consensus if even one process may crash (the FLP result). Real systems assume partial synchrony: the network is usually well behaved, and protocols stay safe even when it isn't.

PapersFischer, Lynch & Paterson, "Impossibility of Distributed Consensus with One Faulty Process," JACM 32(2), 1985 · Lamport, Shostak & Pease, "The Byzantine Generals Problem," ACM TOPLAS 4(3), 1982

Process groups

To survive process failures, a service runs as a group of identical processes that act as one. Clients address the group, not individual members. Members join and leave, and a membership service keeps every member's view of the group consistent. In a flat group, members are peers that decide together: no single point of failure, but every decision needs coordination. In a hierarchical group, a coordinator directs the others: decisions are fast, but the coordinator's failure needs special handling, usually an election.

Primary-backup vs. active replication

In primary-backup (passive) replication, the primary processes requests and ships the resulting state changes to backups. Nondeterministic code is fine, because only the primary runs it. Recovery means detecting the primary's death and promoting a backup, without letting two primaries exist at once.

In active or state machine replication, every replica starts in the same state and applies the same deterministic commands in the same order, so all replicas stay identical. The hard part is agreeing on that order, which is a consensus problem. With 2k + 1 replicas and a majority vote on outputs, the group even masks wrong answers from k faulty replicas.

PapersSchneider, "Implementing Fault-Tolerant Services Using the State Machine Approach: A Tutorial," ACM Computing Surveys 22(4), 1990 · Oki & Liskov, "Viewstamped Replication," PODC 1988

Consensus

Consensus lets a group agree on one value, or a sequence of values, despite failures. A correct protocol guarantees agreement (no two nodes decide differently), validity (the decision was actually proposed), and, when the network behaves, termination. Paxos was the first practical crash-tolerant protocol. Raft was designed to be easier to understand and implement, and is now the most common choice.

Raft in brief

• Leader election: time is divided into numbered terms. A follower that stops hearing from the leader becomes a candidate, increments the term, and asks for votes. A majority of votes makes it leader. Randomized timeouts make split votes rare.
• Log replication: the leader appends each command to its log and sends it to followers. An entry is committed once a majority store it, and only then is it applied to the state machine.
• Safety: a candidate can only win if its log is at least as up to date as a majority's, so a new leader always holds every committed entry.

For Byzantine faults, protocols such as PBFT add extra rounds of voting among 3k + 1 replicas. Blockchains and some permissioned ledgers use descendants of these protocols.

PapersLamport, "The Part-Time Parliament," ACM TOCS 16(2), 1998 · Lamport, "Paxos Made Simple," 2001 · Ongaro & Ousterhout, "In Search of an Understandable Consensus Algorithm," USENIX ATC 2014 · Castro & Liskov, "Practical Byzantine Fault Tolerance," OSDI 1999 · Howard & Mortier, "Paxos vs Raft: Have We Reached Consensus on Distributed Consensus?" PaPoC 2020
ExploreRaft visualization and resources

Detecting failure

Most systems detect failure with heartbeats: each node periodically signals that it is alive, and a monitor suspects any node silent for longer than a timeout.

Choosing the timeout is a trade-off. Short timeouts detect real crashes quickly but cause false positives, such as declaring a node dead during a garbage-collection pause, which can trigger needless failovers or even two leaders. Long timeouts are safe but leave the service degraded longer. Better detectors adapt:

• φ accrual detectors output a suspicion level computed from the observed distribution of heartbeat intervals, instead of a yes/no verdict. Each application then chooses its own threshold.
• SWIM has each member probe a random peer, and ask others to probe indirectly when a direct probe fails. It spreads membership changes by gossip, so detection cost per member stays constant as the group grows.

Chandra and Toueg showed that consensus becomes solvable once a failure detector is only "eventually" accurate. Detectors may make mistakes for a while, provided they eventually stop suspecting some correct process.

PapersChandra & Toueg, "Unreliable Failure Detectors for Reliable Distributed Systems," JACM 43(2), 1996 · Hayashibara et al., "The φ Accrual Failure Detector," SRDS 2004 · Das, Gupta & Motivala, "SWIM," DSN 2002

Distributed commit

A transaction that updates data on several machines must commit everywhere or nowhere. Two-phase commit (2PC) achieves this with a coordinator:

A participant that votes yes promises it can commit, so it must log its changes durably before voting. It then gives up the right to decide alone. If the coordinator crashes after collecting votes but before announcing the decision, the participants are blocked. They hold locks and can neither commit nor abort until the coordinator recovers. Two remedies exist:

• Three-phase commit adds a pre-commit round so participants can decide among themselves. It assumes bounded network delays and is rarely used.
• Replicating the coordinator with consensus (Paxos Commit, or running 2PC across Raft groups as Spanner and CockroachDB do) means a single crash no longer blocks the transaction.

PapersGray, "Notes on Data Base Operating Systems," 1978 · Skeen, "Nonblocking Commit Protocols," SIGMOD 1981 · Gray & Lamport, "Consensus on Transaction Commit," ACM TODS 31(1), 2006

Checkpoints and recovery

Backward recovery returns a failed component to an earlier correct state and continues from there. Forward recovery moves to a new correct state, for example by using error-correcting codes or a compensating action. Backward recovery is more general and depends on checkpoints: saved snapshots of state.

In a distributed system, restoring one process's checkpoint isn't enough. The set of checkpoints restored must form a consistent cut: no process may have recorded receiving a message that its sender, after rollback, never sent. Such a message is an orphan. If processes checkpoint independently, rolling back one can create orphans that force others back too. That chain reaction is the domino effect.

Three strategies avoid this. In coordinated checkpointing, processes snapshot together so the set is consistent by construction. The Chandy–Lamport algorithm does this without stopping the system, using marker messages. In communication-induced checkpointing, processes take extra checkpoints when message patterns would otherwise risk a domino effect. In message logging, processes record the messages they receive, so a single failed process can replay them after restoring its checkpoint while others keep running.

PapersChandy & Lamport, "Distributed Snapshots: Determining Global States of Distributed Systems," ACM TOCS 3(1), 1985 · Elnozahy, Alvisi, Wang & Johnson, "A Survey of Rollback-Recovery Protocols in Message-Passing Systems," ACM Computing Surveys 34(3), 2002

Resilience patterns

Real outages rarely come from a clean crash. They come from slow dependencies, retry storms, and partial failures that health checks miss. A few service-level patterns limit the damage:

Timeouts

Every remote call gets a deadline, so a hung dependency can't hold threads forever.

Retries with backoff and jitter

Retry transient errors, spaced out and randomized so clients don't stampede a recovering service.

Circuit breakers

After repeated failures, stop calling a dependency for a while and fail fast or degrade gracefully.

Bulkheads

Isolate resources (thread pools, connections, cells) so one failing part can't exhaust the rest.

Load shedding

Reject excess work early when overloaded, instead of queueing it until everything times out.

Chaos engineering

Inject failures deliberately in testing or production to prove these mechanisms work.

Recent research names two failure modes these patterns target. In gray failure, a component is degraded in a way some observers see and others don't. A node may pass its health checks while failing real requests. In metastable failure, a system stays down after the trigger is gone, because work amplification such as retries keeps it overloaded. Recovery then requires shedding load, not just fixing the original fault.

PapersHuang et al., "Gray Failure: The Achilles' Heel of Cloud-Scale Systems," HotOS 2017 · Bronson et al., "Metastable Failures in Distributed Systems," HotOS 2021 · Huang et al., "Metastable Failures in the Wild," OSDI 2022 · Gunawi et al., "Why Does the Cloud Stop Computing?" SoCC 2016 · Alquraan et al., "An Analysis of Network-Partitioning Failures in Cloud Systems," OSDI 2018
ReadFowler, "Circuit Breaker" · Timeouts, retries, and backoff with jitter · Avoiding insurmountable queue backlogs

In practice

Tools and reading