What makes distributed systems hard

A distributed system is a collection of independent computers that appears to its users as a single coherent system. That definition, from Tanenbaum and van Steen, captures both the promise and the difficulty. The promise is that many ordinary machines, connected by a network, can provide more capacity, more storage and more reliability than any one machine could. The difficulty is the word appears: the machines do not share memory or a clock, messages between them can be delayed, reordered or lost, and any machine can fail at any moment while the others carry on. Leslie Lamport put the problem memorably in a 1987 email: a distributed system is one in which the failure of a computer you did not even know existed can render your own computer unusable.

Every large service you use is a distributed system. A search query fans out to thousands of machines holding pieces of an index. A payment passes through an authorization service, a fraud model, a ledger and a notification system, each replicated across data centers. A chat message is written to a replicated log before your friend's phone sees it. This course is about how such systems are built so that they keep working, and keep giving correct answers, when parts of them fail. It builds on CMPUT-379, which covered processes, threads, locks and the operating system's view of one machine, and on CMPUT-313, which covered the network protocols that carry messages between machines. We will cite those courses rather than repeat them, and we will point to CMPUT-291 for single-node transactions, to CMPUT-404 for web architecture, to AI-480 for distributed training and to the DCE program for the physical side of data centers.

Throughout the course we follow one invented service, Ledgerline, a payments ledger that small businesses use to record invoices, payments and refunds. Ledgerline must never lose a recorded payment, must never record one twice, and must keep answering while machines, racks and even whole data centers fail. Each lesson adds a piece of its design, and the capstone in lesson 12 assembles them into a geo-distributed service.

Why distribute at all?

There are four main reasons to build a distributed system rather than buy a bigger computer. The first is scale: no single machine can store the web or serve a billion users, and beyond a point a bigger machine costs far more than several ordinary ones. The second is fault tolerance: a single machine is a single point of failure, while a replicated service survives the loss of some replicas. The third is latency: users are spread across the world, and light in fiber travels only about 200 km per millisecond, so a server near the user answers faster than one on another continent. The fourth is that some problems are inherently distributed: a bank's branches, a fleet of vehicles or a network of sensors are already in different places, and the system must connect them.

Transparency deserves a comment. Early distributed systems research aimed to hide distribution completely, making a remote call look exactly like a local one. Experience showed that total transparency is neither achievable nor desirable. A 1994 paper by Waldo, Wyant, Wollrath and Kendall, A Note on Distributed Computing, argued that latency, memory access, partial failure and concurrency make remote operations fundamentally different from local ones, and that pretending otherwise produces fragile systems. Modern practice hides what can be hidden, such as where a replica is located, and exposes what cannot, such as the possibility that a call times out.

The fallacies of distributed computing

In the 1990s, engineers at Sun Microsystems, notably L. Peter Deutsch and later James Gosling, collected a list of false assumptions that programmers new to distributed systems tend to make. The list has become known as the eight fallacies of distributed computing. Each fallacy, if believed, leads to a characteristic kind of bug.

The first fallacy is the most important for this course. Lesson 11 of CMPUT-313 explained how TCP provides reliable, ordered delivery over an unreliable network, but TCP's guarantee is limited: it delivers bytes in order while the connection lasts. When a connection breaks, the sender cannot know which of its last messages arrived and were acted upon. Every protocol in this course must cope with that uncertainty.

Partial failure and the problem of not knowing

On a single computer, failure is usually total: if the power goes, every process stops together, and when the machine restarts it can examine a consistent state on disk. In a distributed system, failure is partial. One machine crashes while others run; a network link fails so that some machines can talk to each other and others cannot; a machine pauses for several seconds during garbage collection and then resumes as though nothing happened. The defining difficulty is that a machine generally cannot tell which of these has happened. If node A sends a request to node B and receives no reply, the possibilities include: the request was lost; B crashed before processing it; B processed it and crashed before replying; B is processing it slowly; the reply was lost; or the reply is merely delayed. From A's point of view these are indistinguishable. A can wait longer or give up, but it cannot know.

This leads to the central technique of the field, the timeout, and to its central weakness. A timeout converts the absence of a message into a suspicion of failure. If the timeout is short, A will often suspect B wrongly, while B is merely slow; if it is long, A will take a long time to react to real failures. No choice of timeout is correct in all circumstances, and much of the cleverness in later lessons, from failure detectors in lesson 11 to leader election in lesson 9, is about acting safely on suspicions that may be wrong.

System models

To reason about distributed algorithms we need precise assumptions about what can go wrong. A system model specifies assumptions about timing and about failures. The choice of model determines which problems are solvable at all: some problems that are easy in one model are provably impossible in another.

Timing assumptions come in three main forms. In the synchronous model there are known upper bounds on message delay, on the time a process takes for a step, and on clock drift. Algorithms can then use timeouts with certainty: if no reply arrives within the bound, the sender has definitely crashed. In the asynchronous model there are no bounds at all; messages are eventually delivered, but may take arbitrarily long. This is the safest model to design for, because an algorithm correct in it is correct whatever the timing, but it is also the most restrictive: lesson 8 shows that consensus cannot be solved deterministically in an asynchronous system if even one process may crash. The partially synchronous model, introduced by Dwork, Lynch and Stockmeyer in 1988, sits between: the system behaves asynchronously for an unknown period but eventually respects bounds that are themselves unknown. This is the model that most practical protocols, including Paxos and Raft, assume for progress, while relying only on asynchrony for safety.

Failure assumptions form a hierarchy. In the crash-stop model a process works correctly until it halts, and never returns. In the crash-recovery model a process may halt and later restart, losing its memory but keeping whatever it wrote to stable storage; this is the realistic model for servers that reboot. In the omission model a process may fail to send or receive some messages. In the Byzantine model, named after Lamport, Shostak and Pease's 1982 paper on the Byzantine generals, a faulty process may behave arbitrarily, including lying, sending conflicting messages to different peers or colluding with other faulty processes. Byzantine faults model bugs, corrupted hardware and malicious participants. Tolerating them costs much more: lesson 8 shows that crash-tolerant consensus needs \(2f + 1\) replicas to survive \(f\) failures, while Byzantine-tolerant consensus needs \(3f + 1\).

Networks have failure modes too. A network partition splits the machines into groups that can communicate within a group but not between groups. Partitions happen more often than intuition suggests: a 2014 study by Bailis and Kingsbury collected dozens of publicly reported partitions caused by switch failures, misconfigurations and software bugs, and cloud providers report them regularly. A partition is especially dangerous because each side may believe the other has crashed and carry on independently, the situation called split brain. Lesson 7's CAP theorem is fundamentally a statement about what a system can promise during a partition.

Scale makes rare events common

A component that fails once every three years seems reliable. In a fleet of a hundred thousand machines, it fails about ninety times a day. Large operators therefore design on the assumption that something is always broken. The next program makes this concrete.

# Failures are normal at scale: expected failures per day in a fleet of machines.
import math

def p_at_least_one(p_each, n):
    return 1 - (1 - p_each) ** n

# Suppose a single server has a 3-year mean time between failures (MTBF).
mtbf_days = 3 * 365
p_day = 1 - math.exp(-1 / mtbf_days)          # chance one server fails on a given day
print(f"one server fails on a given day with probability {p_day:.5f}")
for n in (10, 100, 1000, 10000, 100000):
    expected = n * p_day
    print(f"{n:6d} servers: expected failures/day = {expected:7.2f}, "
          f"P(at least one today) = {p_at_least_one(p_day, n):6.1%}")

one server fails on a given day with probability 0.00091
    10 servers: expected failures/day =    0.01, P(at least one today) =   0.9%
   100 servers: expected failures/day =    0.09, P(at least one today) =   8.7%
  1000 servers: expected failures/day =    0.91, P(at least one today) =  59.9%
 10000 servers: expected failures/day =    9.13, P(at least one today) = 100.0%
100000 servers: expected failures/day =   91.28, P(at least one today) = 100.0%

A related effect concerns latency rather than failure. Jeffrey Dean and Luiz André Barroso described it in The Tail at Scale (2013). When a user request fans out to many servers in parallel, as a search query does, the request completes only when the slowest server replies. If each server is slow on 1 percent of requests, a request that touches one server is slow 1 percent of the time, but one that touches a hundred servers is slow 63 percent of the time. Rare slowness in a component becomes common slowness for the system.

# The "tail at scale": a request that fans out to many servers waits for the slowest one.
import random
random.seed(450)

def server_latency_ms():
    # Most replies take about 10 ms; 1 in 100 hits a slow path (garbage collection,
    # a busy disk, a queue behind a large request) and takes about 1 second.
    if random.random() < 0.01:
        return random.uniform(800, 1200)
    return random.gauss(10, 2)

def request(fanout):
    # The user-facing request finishes only when every sub-request has replied.
    return max(server_latency_ms() for _ in range(fanout))

TRIALS = 20000
print("fan-out   median ms   p99 ms   share of requests over 500 ms")
for fanout in (1, 10, 100, 1000):
    lat = sorted(request(fanout) for _ in range(TRIALS // max(1, fanout // 10)))
    n = len(lat)
    slow = sum(1 for x in lat if x > 500) / n
    print(f"{fanout:7d} {lat[n // 2]:11.1f} {lat[int(n * 0.99)]:8.1f}   {slow:8.1%}")

# The same effect computed exactly: P(at least one slow reply) = 1 - 0.99^fanout
for fanout in (1, 10, 100, 1000):
    print(f"exact P(slow) for fan-out {fanout:4d}: {1 - 0.99 ** fanout:.1%}")

fan-out   median ms   p99 ms   share of requests over 500 ms
      1        10.0     16.9       0.9%
     10        13.2   1162.0       9.4%
    100       924.0   1197.0      63.6%
   1000      1174.6   1199.7     100.0%
exact P(slow) for fan-out    1: 1.0%
exact P(slow) for fan-out   10: 9.6%
exact P(slow) for fan-out  100: 63.4%
exact P(slow) for fan-out 1000: 100.0%

The simulation shows the tail moving first. With one server the 99th percentile is about 17 ms; with ten servers the median is still about 13 ms but the 99th percentile is over a second; with a hundred servers even the median request waits for a slow reply, and the simulated share of slow requests matches the exact value \(1 - 0.99^{n}\). Dean and Barroso described techniques to tame the tail: hedged requests, which send a second copy of a request to another replica if the first has not replied within, say, the 95th-percentile latency, and then use whichever reply arrives first; tied requests, which send to two replicas at once and let the second cancel itself when the first starts work; and micro-partitioning, so that slow servers can shed load quickly. These are distributed systems techniques in miniature: they accept that individual components misbehave and engineer the whole to behave well anyway.

Safety and liveness

Correctness properties of distributed algorithms are usually split into two kinds, a distinction formalized by Lamport and by Alpern and Schneider. A safety property says that something bad never happens: two nodes never both believe they are leader in the same term; a payment is never recorded twice; a read never returns a value that was never written. A liveness property says that something good eventually happens: every request eventually receives a reply; a new leader is eventually elected after a crash. Safety properties can be violated at a specific moment, and the violation cannot be undone. Liveness properties can only be violated over an infinite execution, because there is always hope that the good thing will happen later.

The distinction matters because the two kinds of property respond differently to bad conditions. Well-designed protocols keep safety under all conditions, however asynchronous the network or however many timeouts fire wrongly, and guarantee liveness only when conditions are reasonably good: a majority of nodes are up and messages are delivered within some bound for long enough. This is exactly the design of Paxos and Raft. When you read a protocol, the first questions to ask are which properties are safety properties, which are liveness properties, and under what assumptions each holds.

Building blocks and a map of the course

Distributed systems are built from a small number of recurring ideas, which the rest of the course develops. Lesson 2 covers communication: remote procedure calls, messaging, timeouts, retries and idempotency. Lesson 3 covers time: why physical clocks cannot be trusted for ordering, and how logical clocks capture causality. Lesson 4 uses those clocks to record consistent global states and to coordinate, through mutual exclusion and leader election. Lesson 5 covers distributed transactions, where several machines must commit or abort together. Lessons 6 and 7 cover replication and the consistency models that describe what replicated data looks like to clients, including the CAP theorem. Lessons 8 and 9 cover consensus, the problem at the heart of fault-tolerant replication, through Paxos and Raft. Lesson 10 covers partitioning and scaling. Lesson 11 covers fault tolerance in practice: failure detection, resilience patterns and site reliability engineering. Lesson 12 assembles the pieces into a geo-distributed design for Ledgerline.

One more piece of orientation. Distributed systems is a field where informal reasoning fails often and expensively. Protocols that look obviously correct contain subtle bugs that appear only under rare interleavings of messages and failures. Practitioners therefore lean heavily on precise specifications, on proofs, on model checking with tools such as TLA+, on deterministic simulation testing, and on adversarial testing that injects partitions and crashes, such as Kyle Kingsbury's Jepsen analyses. We will use small, seeded simulations in Python throughout the course for the same reason: a simulation lets us watch an algorithm under failures that would be hard to arrange on real machines, and replay exactly the same scenario.

Worked examples