Skip to content
Tutorials Center
My learning

Topics

Lesson 3 of 36 ยท Getting Started

Failure and System Models

Learn crash-stop, crash-recovery, omission and Byzantine failures, plus synchronous and asynchronous timing models, with a failure-injection simulator.

You cannot design or prove anything about a distributed system without saying what can go wrong. "Handles failures" is not a specification; "tolerates up to two nodes crashing permanently, on a network that may drop messages" is. A system model is exactly such a statement: a precise list of the assumptions about nodes, the network and timing that an algorithm relies on.

Models are simplifications on purpose. Real hardware is messier than any model, but an algorithm that is correct in a clear model, and a model that is honest about reality, give you a solid foundation. This lesson covers the three parts of a model (node failures, network behavior, timing) and then lets you inject failures into a small cluster and see their effects.

Faults and failures

Two words that sound alike are used carefully in this field.

  • A fault is something going wrong in one component: a disk error, a crashed process, a lost message.
  • A failure is when the system as a whole stops delivering its service to users.

The aim of fault tolerance is to prevent faults from turning into failures. A cluster where one of five nodes crashed has a fault but no failure, as long as the service still answers correctly. You can never reduce the fault rate to zero, so you design for tolerating faults, and you test that by causing them on purpose (see testing distributed systems).

Node failure models

A node failure model says how a node is allowed to misbehave. They are ordered from the most gentle to the most hostile:

Four ways a node can fail

Crash-stop Works correctly, then stops forever.
Crash-recovery Stops, then restarts. Disk survives, memory does not.
Omission Works, but sometimes fails to send or receive.
Byzantine Anything at all, including lying.

Each model includes all the gentler ones.

1 / 2

Crash-stop. The node behaves correctly until the moment it halts, and it never comes back. It never does anything wrong; it just stops. This is the simplest model and good for explaining algorithms, but real machines are usually restarted.

Crash-recovery. The node may crash and later restart. What it remembers depends on what it saved to stable storage (disk) before the crash: anything only in memory is gone. This is the realistic model for most servers, and the reason databases write logs to disk before acknowledging.

Omission. The node keeps running but sometimes fails to send or receive a message, for example because a buffer overflowed. From the outside it can look like a crash, and you cannot distinguish the two for certain.

Byzantine. The node can do anything: send contradictory answers to different peers, corrupt data, or act maliciously after being hacked. The name comes from the "Byzantine generals" problem. Tolerating this is costly: protocols need more than 3f nodes to survive f Byzantine nodes, and so most internal systems assume nodes are faulty but not malicious. Blockchains and systems with mutually untrusting parties do need it.

Network failure models

The network has models too. In the most common one, called a fair-loss link, a message may be lost, but if you keep resending it, it eventually arrives. Layering retries and deduplication on top gives a reliable link (a "perfect link": no loss, no duplication, no invented messages). In the worst case, the network can partition, splitting nodes into groups that cannot reach each other for a while. We will meet partitions again in CAP.

Timing models

How much do we assume about time? Three classic answers:

Model Assumption Realism
Synchronous Known upper bounds on message delay, processing time and clock drift Rarely true on the Internet
Asynchronous No bounds at all: any message may take arbitrarily long Safe, but you can never tell slow from dead
Partially synchronous The system behaves synchronously most of the time, with unknown periods of chaos A good match for real networks

In a synchronous system, a timeout is a perfect failure detector: if no reply arrives in the maximum delay, the node has crashed. In an asynchronous system no timeout is ever safe, because the reply might just be late. Famous results (such as the FLP impossibility) show that some problems cannot be solved with guarantees in a fully asynchronous system, and algorithms like Raft and Paxos work in the partially synchronous model: always safe, and live once the network behaves for long enough.

Safety means "nothing bad ever happens" (two nodes never decide different values). Liveness means "something good eventually happens" (a decision is eventually made). Good algorithms keep safety under every failure and trade away only liveness when the network is bad.

Slow looks like dead

Let us see why timeouts are guesses. Here a client waits for replies from a node whose delays are drawn from a skewed distribution (usually fast, sometimes very slow), with one extra scenario where the node has really crashed. We try several timeout values and count the mistakes: healthy nodes wrongly declared dead (false positives), and crashed nodes that we were slow to notice.

Python Choosing a timeout is a trade-off

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

A short timeout notices a real crash quickly but wrongly suspects healthy, momentarily slow nodes. A long timeout almost never makes that mistake but leaves users waiting for a dead node. No setting is correct in an asynchronous world; you pick one using measured latencies, and design the rest of the system so a wrong guess is harmless. The failure detector lesson improves on a plain timeout.

A failure-injection simulator

Now let us feel the models. We run a small replicated register: five replicas each store a value, and a client reads by asking all of them and trusting the answer given by a majority. We then inject each kind of failure and check whether the client still gets the right answer.

Python Injecting failures into five replicas

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Read the output carefully. With a majority of five (3 nodes) correct and reachable, the read is right even if two replicas crash, drop messages or lie. Lose the majority and the read stops, but notice it stops with a clear "no majority" instead of returning wrong data, which is safety kept, liveness lost. In the Byzantine case, the honest value still wins here because 3 of 5 agree. This is a toy: real Byzantine tolerance needs authenticated messages and several rounds, since a lying node can tell different lies to different peers.

The last lines show crash-recovery: the memory-only write vanished on restart. This is why real systems flush a write-ahead log before acknowledging a write.

Choosing a model

For most business systems the sensible choice is: crash-recovery nodes, fair-loss network that can partition, partially synchronous timing. That is the model behind Raft and the replicated databases built on it. State your model whenever you design or read about a system. When someone claims their protocol "handles all failures", ask: which failures, and under which timing assumptions?

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What is the difference between a fault and a failure?

    Fault tolerance means keeping component faults from becoming system failures, for example by replicating data across several nodes.
  2. 2. Which node failure model lets a node lose its memory on a restart but keep its disk contents?

    In crash-recovery a node may restart, and only what it saved to stable storage survives, which is why databases log to disk before acknowledging writes.
  3. 3. In an asynchronous system, why can a timeout not tell you for certain that a node has crashed?

    With no bound on delays, a missing reply could be a crash or just a very slow node. That is why failure detection is only ever a guess.
  4. 4. Which pairing describes the realistic model most real-world consensus systems assume?

    Raft and Paxos assume nodes may crash and restart, messages may be lost or delayed, and the system is eventually stable enough to make progress.
  5. 5. In the five-replica simulation, why does the read return "no majority" instead of a wrong value when three replicas crash?

    Requiring a majority keeps the answer safe; when too few nodes respond the system gives up liveness (no answer) rather than risk an incorrect one.

Summary

  • A system model lists assumptions about node failures, the network and timing; algorithms are only correct relative to a model.
  • A fault is a component problem; a failure is the whole service going wrong.
  • Node models grow harsher: crash-stop, crash-recovery, omission, Byzantine.
  • Timing models: synchronous (bounds known), asynchronous (no bounds), partially synchronous (usually bounded), the realistic middle.
  • Timeouts are guesses: short ones cause false suspicions, long ones slow detection.
  • Majorities protect safety; when they are lost, a good system stops rather than answers wrongly.

Next: Physical Clocks, Drift and Skew, the first of the problems that start with "each node has its own clock".