---
source: 'https://howaiworks.ai/glossary/distributed-computing'
section: glossary
title: Distributed Computing
description: >-
  Distributed computing splits work across separate machines that talk only by
  messages. Why partial failure, not speed, is the defining problem.
tags:
  - Distributed Computing
  - distributed systems
  - fault tolerance
  - Scaling
  - AI Infrastructure
  - Performance
category: Infrastructure & Hardware
datePublished: '2025-08-20'
lastUpdated: '2026-07-22'
---

# Distributed Computing

> Distributed computing splits work across separate machines that talk only by messages. Why partial failure, not speed, is the defining problem.

## 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](https://howaiworks.ai/glossary/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](https://howaiworks.ai/glossary/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](https://howaiworks.ai/glossary/consensus-algorithm) 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](https://howaiworks.ai/glossary/inference) pipeline outgrow one
machine without having the lockstep structure of
[distributed training](https://howaiworks.ai/glossary/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](https://howaiworks.ai/glossary/consensus-algorithm) 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](https://howaiworks.ai/glossary/inference) fleet is a fan-out service and inherits the tail arithmetic
verbatim. Disaggregated serving moves the [KV cache](https://howaiworks.ai/glossary/kv-cache) between machines, turning
a memory-locality question into a network one. An [agent](https://howaiworks.ai/glossary/ai-agent) calling tools across
several services is a distributed transaction without the transaction, and a
[multi-agent system](https://howaiworks.ai/glossary/multi-agent-systems) that must reach a joint decision has reinvented
[consensus](https://howaiworks.ai/glossary/consensus-algorithm) 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.

```python
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.

## Frequently Asked Questions

### What is distributed computing in simple terms?

It is any arrangement where several separate computers, connected only by a network, cooperate on one job and present themselves to the user as a single system. The computers share no memory and no clock, so everything they know about each other arrives as a message that may be delayed, duplicated or lost.

### What makes distributed computing different from ordinary programming?

Partial failure. On one machine a program either runs or it crashes; in a distributed system one participant can die while the rest carry on, and the survivors cannot tell a dead machine from a slow one — both look like silence. Nearly every technique in the field exists to cope with that ambiguity.

### What is the difference between distributed computing and parallel processing?

Parallel processing splits work across processors that share memory inside one machine, where coordination costs nanoseconds and a failure takes down everything at once. Distributed computing splits work across machines that share nothing, where coordination costs milliseconds and each machine can fail on its own.

### What does the CAP theorem actually say?

It says that when the network partitions — messages between two groups of machines stop getting through — a replicated system must choose between refusing to answer, to stay consistent, and answering with possibly stale data, to stay available. It is not a claim that you may only ever have two of three properties.

### Why can a system of fast machines be slow?

Because a request that fans out to many machines and waits for all of them inherits the worst response among them, not the average. A server that is slow 1% of the time is a good server; ask 100 of them in parallel and 63% of requests hit at least one slow reply. Nothing got slower — the shape of the request did.

### What are some real examples of distributed computing?

Kubernetes clusters, Apache Spark jobs, Cassandra and DynamoDB databases, Google's Spanner, content delivery networks, blockchains, and volunteer projects like Folding@home. Every large web service you use is one, and so is every cluster training or serving a large AI model.

## Related

### Related terms

- [Consensus Algorithm](https://howaiworks.ai/glossary/consensus-algorithm)
- [Distributed Training](https://howaiworks.ai/glossary/distributed-training)
- [Parallel Processing](https://howaiworks.ai/glossary/parallel-processing)
- [Concurrency](https://howaiworks.ai/glossary/concurrency)
- [Cloud Computing](https://howaiworks.ai/glossary/cloud-computing)
- [AI Infrastructure](https://howaiworks.ai/glossary/ai-infrastructure)

---

Source: https://howaiworks.ai/glossary/distributed-computing — HowAIWorks.ai