Distributed Computing

Definition

Distributed computing is what happens whenever a single job is split across separate computers that can only reach each other by sending messages over a network. Load a web page, tap a card at a till, ask a chatbot a question: the answer is assembled by dozens of machines in different racks and often on different continents, cooperating closely enough that you experience one system.

What makes this a distinct field rather than "programming, but with more computers" is one property: partial failure. A program on a single machine either runs or it crashes, and when it crashes everything about it stops at once. A distributed system has no such courtesy. One participant can die while the others carry on — and the survivors have no way to tell a machine that has died from a machine that is merely slow, or from a network that quietly dropped the messages between them. All three look identical from the outside: silence.

Leslie Lamport put it best in 1987: "A distributed system is one in which the failure of a computer you didn't even know existed can render your own computer unusable."

Here is why that matters in numbers rather than aphorisms. Suppose every service you depend on is individually excellent — 99.9% available, which is about 43 minutes of downtime a month. Chain ten of them so that a user request needs all ten to work, and your availability is 0.999¹⁰ = 99.0%. Ten "three nines" components in series make a "two nines" product. Fan a request across fifty of them, as a large microservice estate routinely does, and you get 0.999⁵⁰ = 95.1% — roughly 35 hours a month in which something in the path is broken. Nobody wrote a bug. Reliability simply does not survive multiplication, and a design that assumed it would is now the outage.

That is the trade the whole field is about. Distributing work buys capacity larger than any single machine and survival of any single machine's death. It costs you the ability to reason about your program as one thing that either works or does not.

How It Works

Everything the machines know about each other is a message

Inside one computer, two threads coordinate through shared memory: a write becomes visible in nanoseconds, and if the machine dies, both die together. Take that away and one primitive is left — send a message, hope it arrives. It may be delayed, reordered, duplicated or lost, and none of those events announce themselves. The first of Peter Deutsch's 1994 fallacies of distributed computing is exactly this: the network is reliable, and believing it is the most common way to ship a broken system.

So a timeout is a guess, and it is the only failure detector you have. When a machine stops replying you must eventually decide it is dead and act — reassign its work, elect a new leader, fail the request. Set the timeout short and you will regularly declare a healthy but busy machine dead, then run its job twice. Set it long and every real crash costs you that long in stalled work. No setting is right, because the information needed to be right does not exist. This is where concurrency's tools stop: a mutex protects shared memory, and there is no shared memory here to protect.

Without a shared clock, "before" is a guess too

Machines synchronised with NTP typically agree to within a few milliseconds inside a data centre and tens of milliseconds across the internet — and their clocks can jump backwards when a correction lands. If machine A stamps an event at 12:00:00.003 and machine B stamps one at 12:00:00.001, you cannot conclude B's happened first. For events milliseconds apart on different hosts, wall-clock timestamps are not evidence.

One answer is to stop using time and use causality: Lamport timestamps and vector clocks order events by which could possibly have influenced which, leaving genuinely concurrent events unordered rather than falsely ranked. The other is to make the uncertainty explicit and pay for it. Google's Spanner (OSDI 2012) exposes a clock API returning an interval rather than an instant, with the error bound held under about ten milliseconds by GPS receivers and atomic clocks in every data centre — and then deliberately waits out that interval before committing, so no two transactions can be misordered. It buys global ordering with latency, the only currency available.

Agreement is the expensive operation, and its price is a map

When replicas must agree — on who the leader is, on whether a transaction committed — they run a consensus algorithm, and every decision costs at least one network round trip to the nearest majority. That floor is the speed of light, not the software: New York to London cannot beat 56 ms, while the same protocol inside one data centre completes in well under a millisecond.

The consequence for design is that where you put replicas is a latency decision before it is a reliability one. Spreading them across continents to survive a regional outage means every coordinated write pays the crossing. That is why the rest of this page is largely about arranging not to coordinate — and why the next section is about what you may safely do instead.

Replication forces a choice, and a partition makes you take it

Copy your data to three machines and you survive losing one. You have also created the possibility that the copies disagree. The CAP theorem — Eric Brewer's 2000 conjecture, proved by Gilbert and Lynch in 2002 — states the resulting constraint precisely, and it is almost always misquoted. It does not say "pick two of three". It says that while the network is partitioned, so that two groups of replicas cannot exchange messages, a system must choose between refusing to answer (staying consistent) and answering from whatever it has (staying available). With no partition you can have both.

Most systems make that choice tunable per operation with quorums. Across N replicas, a write acknowledged by W of them and a read consulting R of them are guaranteed to overlap — and so to see the latest write — provided R + W > N. Amazon's Dynamo paper (SOSP 2007) reports (N,R,W) = (3,2,2) as the common production setting: any one machine may be down for either operation and reads still see writes. Set R=1, W=1 and both get faster while the guarantee evaporates.

Fan-out makes a system of fast machines into a slow system

The most counter-intuitive arithmetic in distributed computing concerns the tail, not the average. Jeff Dean and Luiz Barroso's The Tail at Scale (CACM, 2013) gives the canonical worked case: a server that answers in about 1 ms typically but has a 99th-percentile latency of one second. Send a request to one such server and 1% of users wait a second. Now have each request gather results from 100 of them in parallel and wait for all — a shape that describes search, recommendation and most AI serving stacks. The chance that every replica is fast is 0.99¹⁰⁰ = 0.366, so 63% of requests now take more than a second.

Nothing got slower. The same machines, with the same 99th percentile, produced a system whose median is worse than any single component's tail, because a fan-out request inherits the worst of everything it touched. That is why large systems invest so heavily in hedged requests, replica selection and cancelling redundant work — and why fanning out more widely than you must is a design mistake rather than a scaling strategy.

Real-World Applications

Google's infrastructure papers are the field's engineering canon. The Google File System (SOSP 2003) opened by treating component failure as the normal case rather than an exception, and replicated every chunk three times by default. MapReduce (OSDI 2004) made a whole class of jobs survivable by re-executing failed tasks elsewhere. Chubby (OSDI 2006) packaged Paxos as a lock service so that other teams would stop writing their own consensus badly; Bigtable and later Spanner built storage on top. Together they moved distributed computing from a research topic to something an ordinary engineering team could adopt, and their open descendants — HDFS, ZooKeeper, etcd — run underneath a large share of everything.

Apache Spark chose recomputation over replication. A Spark job is a graph of transformations over partitioned datasets, and the system records the lineage of every partition: the exact sequence of operations that produced it. When a machine dies mid-job, Spark does not restore from a replica; it re-runs the lineage for the lost partitions on a surviving machine. Fault tolerance becomes a property of how the computation is described, which is a genuinely different answer to partial failure than keeping spare copies.

Kubernetes is partial failure turned into a control loop. You declare the state you want — ten replicas of this container — and controllers continuously compare it against observed state and act on the difference, forever. Cluster state lives in etcd, which is Raft, so a majority of etcd members must be reachable for anything to be decided. And the ambiguity from the Definition shows up in the open: when a node stops sending heartbeats, the control plane waits a grace period and then declares it gone and reschedules its pods elsewhere. If the node was actually alive and merely unreachable, the workload is now running twice — which is why anything that must not run twice needs a lease or a fencing token rather than the scheduler's word.

Ray carries the same ideas into AI workloads. It exposes remote functions and stateful actors whose results are distributed futures, schedules them across a cluster, and reconstructs lost objects from lineage in the Spark tradition — what a team reaches for when reinforcement-learning rollouts, hyperparameter sweeps or a batch inference pipeline outgrow one machine without having the lockstep structure of distributed training.

Volunteer computing is the opposite extreme, and the example most people already know. SETI@home and its successors on the BOINC platform handed independent work units to millions of home PCs, with no coordination between them and no consequence to losing one. Folding@home's volunteer network passed one exaFLOP of aggregate throughput in April 2020 — more raw compute than the fastest single supercomputer of the day — precisely because protein-folding simulations need no agreement about anything. When the work is genuinely independent, distribution is nearly free. Every hard problem on this page comes from work that is not.

Key Concepts

• Partial failure is the whole subject. Every other item here is a response to it. If you cannot say what your system does when one participant vanishes mid-operation, you have not designed a distributed system, you have deployed one.
• Exactly-once delivery does not exist; exactly-once effects do. A sender that gets no reply cannot know whether the request was lost or the reply was, so it must retry, so the receiver must expect duplicates. The workable pattern is at-least-once delivery plus idempotent operations — "set the balance to 100" can be applied five times safely, "add 20 to the balance" cannot.
• What you assume can go wrong is a design input, not a detail. Most infrastructure is built against crash-stop (a machine halts and stays halted) or crash-recovery (it comes back with stale state, which is why nodes write durably before acknowledging). Harder is omission — a machine that can receive but not send looks alive to itself and dead to everyone else. Hardest is Byzantine, where a participant may lie or contradict itself; Lamport, Shostak and Pease named it in 1982, and tolerating it costs 3f+1 participants where a crash costs 2f+1.
• Fencing tokens are what you use when a quorum is not available. Two nodes each convinced they are the leader will both write, and a majority quorum is the usual prevention. Where there is no quorum to take — a single-writer lock over shared storage, say — a monotonically increasing token carried with every write lets the storage layer itself reject the stale leader's requests after it wakes from a long pause.
• Consistency is a spectrum, not a switch. Linearizable (every read sees the latest write, at the cost of coordination), causal (operations that caused each other are seen in order), and eventual (replicas converge if writes stop) are different products with different latency floors, and picking the strongest one everywhere is how a system inherits the 56 ms above on every call.

Challenges

You cannot observe the system you are debugging. There is no moment at which all machines are in a state you can print, because reading their states takes time during which they change — the reason Chandy and Lamport had to invent a snapshot algorithm in 1985 rather than just taking one. In practice this means bugs that appear only under a particular interleaving of messages, on a particular day, and never reproduce. The whole discipline of distributed tracing exists to reconstruct after the fact what no single machine ever knew.

Retries amplify exactly when you can least afford it. A service slows down, its callers time out and retry, the extra load slows it further, and the system settles into a stable broken state that persists after the original trigger is gone. The arithmetic is brutal when retries stack: if every layer of a five-deep call chain retries three times, one user request can become 3⁵ = 243 backend calls. Retries need jitter, budgets and circuit breakers, or they are a denial-of-service attack you wrote against yourself.

Adding a machine can make the system slower. A wider fan-out raises the tail-latency exposure computed above: every extra participant is another chance to draw somebody's 99th percentile, and the request waits for the worst of them. The same reversal holds wherever machines must coordinate rather than merely serve — a bigger consensus group costs more per decision and commits no faster. Capacity comes from splitting work into more independent groups, never from enlarging one.

Most of the difficulty is operational, not algorithmic. Rolling an upgrade across machines that must interoperate with the old version mid-rollout, migrating a schema without a maintenance window, restoring a partition-tolerant database to a coherent point in time — none of these are hard computer science, and all of them are where the incidents come from. The advice the field has converged on is to distribute only as far as the requirement demands. A single machine that fits your workload has an unbeatable advantage: it cannot half-fail.

Future Trends

The most active direction is avoiding coordination rather than accelerating it, because the 56 ms floor is physics and will not move. Conflict-free replicated data types (CRDTs) restrict operations to those that commute, so replicas can accept writes independently and converge without ever taking a vote — the machinery behind collaborative editors and the "local-first" movement, where the network is treated as an optimisation rather than a prerequisite. Causal consistency is spreading for the same reason: it is the strongest guarantee obtainable without a round trip.

The second is testing that can actually find these bugs. Deterministic simulation — pioneered by FoundationDB, now adopted well beyond it — runs the entire cluster on a single-threaded simulated network with a seeded random schedule, so that message reordering, partitions and clock skew are controlled, and a failure that appears once in a million runs replays exactly. Formal specification is the complement: Amazon reported in Communications of the ACM (2015) that TLA+ found a DynamoDB replication bug whose shortest failing trace was 35 steps, a sequence no reviewer or integration test was going to stumble into.

The third is that AI systems keep re-encountering these problems in new clothes. An inference fleet is a fan-out service and inherits the tail arithmetic verbatim. Disaggregated serving moves the KV cache between machines, turning a memory-locality question into a network one. An agent calling tools across several services is a distributed transaction without the transaction, and a multi-agent system that must reach a joint decision has reinvented consensus with a non-deterministic participant. The vocabulary is forty years old; the systems importing it are new.

Code Example

The three pieces of arithmetic from this page, computed rather than asserted. None of it needs a cluster — that is the point, since each is a property of the shape of a distributed system rather than of its code.

def serial_availability(component: float, n: int) -> float:
    """Availability of a request path that needs all n components to work."""
    return component ** n

def fanout_slow_fraction(p_slow: float, replicas: int) -> float:
    """Chance a scatter-gather request hits at least one slow replica."""
    return 1 - (1 - p_slow) ** replicas

def retry_amplification(retries: int, depth: int) -> int:
    """Backend calls generated by one user request when every layer retries."""
    return retries ** depth

for n in (1, 10, 50):
    a = serial_availability(0.999, n)
    print(f"{n:>3} components at 99.9%: {a:.4%}  ({(1 - a) * 30 * 24:.1f} h/month down)")

for r in (1, 10, 100):
    print(f"fan-out to {r:>3} replicas, 1% slow each: {fanout_slow_fraction(0.01, r):.1%} slow")

print(f"3 retries x 5 layers: {retry_amplification(3, 5)} backend calls per request")

#   1 components at 99.9%: 99.9000%  (0.7 h/month down)
#  10 components at 99.9%: 99.0045%  (7.2 h/month down)
#  50 components at 99.9%: 95.1206%  (35.1 h/month down)
# fan-out to   1 replicas, 1% slow each: 1.0% slow
# fan-out to  10 replicas, 1% slow each: 9.6% slow
# fan-out to 100 replicas, 1% slow each: 63.4% slow
# 3 retries x 5 layers: 243 backend calls per request

Read the middle block as a design rule. A component with a 1% slow tail is a good component; a hundred of them behind one request is a service that is slow most of the time. The fix is never "make the components faster" — it is to fan out less, or to stop waiting for all of them.