Many machines, one system

Why distribute at all

A single computer is simpler to build, reason about, and debug. We give that up for four reasons:

• Capacity. One machine has a ceiling on CPU, memory, storage, and network bandwidth. Past that ceiling, the only way up is out.
• Availability. One machine is one point of failure. Copies on separate machines let the service survive a crash, a power loss, or a bad disk.
• Locality. Users and data are spread across the planet. Placing computation near them cuts latency that no amount of hardware can remove.
• Sharing. Expensive or unique resources (storage arrays, GPUs, datasets) can be pooled and used by many clients.

The price is coordination. Every decision that used to be a memory read now involves a message over a network that can be slow, lossy, or split. Leslie Lamport famously summed up the downside: you can be stopped cold by the failure of a machine you did not know existed.

Go deepervan Steen & Tanenbaum, Distributed Systems (4th ed., free PDF), ch. 1 · Kleppmann, Cambridge lecture notes

Where the distribution lives

The single-system illusion can be built at different layers of the software stack. Where you put it decides how much the machines must have in common and how much the application has to know.

Pure distributed operating systems proved hard to deploy because they demand uniform hardware and full control of every machine. Most systems today reach the same goals through middleware layered on ordinary operating systems. The principles are identical; only the layer changes.

PaperTanenbaum & van Renesse, "Distributed Operating Systems," ACM Computing Surveys 17(4), 1985

Centralized vs. distributed

Defining traits

Every distributed system shares a handful of properties. Most of the field is about coping with the last three.

Resource sharing

Storage, compute, and data on one node are usable from any other.

Openness

Components interoperate through published interfaces and protocols, so parts can be replaced or extended.

Concurrency

Many processes on many nodes run at once and contend for the same resources.

No global clock

Each node has its own clock that drifts. Ordering events requires logical reasoning, not timestamps alone.

Independent failure

Any node or link can fail while the rest keep running, and others may not find out.

Heterogeneity

Different hardware, operating systems, languages, and administrators must still cooperate.

The absence of a shared clock is subtle enough to deserve its own paper. Lamport showed that "happened before" can be defined purely from message flow, and that logical clocks can order events consistently without synchronized time.

PaperLamport, "Time, Clocks, and the Ordering of Events in a Distributed System," CACM 21(7), 1978

Transparency

Transparency is how much of the distribution a system hides. The goal is that users and programmers can treat many machines as one.

When hiding hurts

Full transparency is neither possible nor always desirable. Latency cannot be hidden: a call to another continent is a thousand times slower than a local one, and code written as if it were local will crawl. Failure cannot be fully hidden either, because a node that is slow and a node that is dead look the same from outside. Fischer, Lynch, and Paterson proved that with even one possible crash, no deterministic algorithm can guarantee agreement in an asynchronous network.

PaperFischer, Lynch & Paterson, "Impossibility of Distributed Consensus with One Faulty Process," JACM 32(2), 1985

Scalability

A system scales when it handles more load by adding resources, without a matching loss in performance. There are three distinct dimensions:

• Size: more users, requests, and data.
• Geography: nodes and users far apart, where round-trip time dominates.
• Administration: many independent organizations and policies, as on the internet itself.

Scaling out relies on four techniques that recur throughout the field: partitioning (split data or work so each node owns a slice), replication (copy data for read capacity and resilience), caching (keep hot results near the consumer), and asynchrony (avoid waiting on remote replies). At large scale, the slowest few percent of requests start to dominate user experience, so tail latency becomes a design target in its own right.

PaperDean & Barroso, "The Tail at Scale," CACM 56(2), 2013

Fault tolerance

A fault-tolerant system keeps delivering correct service when components fail. The vocabulary is precise: a fault (a flipped bit, a cut cable) may cause an error in state, which may surface as a failure visible to users. Fault tolerance breaks that chain.

How components fail

Redundancy comes in three forms: information (checksums, erasure codes), time (retry the operation), and physical (extra hardware or processes). Detecting failure is itself uncertain. A timeout can only suspect a crash, and choosing its length trades fast recovery against false alarms.

PapersChandra & Toueg, "Unreliable Failure Detectors for Reliable Distributed Systems," JACM 43(2), 1996 · Lamport, Shostak & Pease, "The Byzantine Generals Problem," TOPLAS 4(3), 1982

Architectural models

How responsibilities are divided among nodes shapes where bottlenecks and failure points appear.

Client–server is easy to secure and manage but concentrates load and failure on the server. Peer-to-peer removes the center, so capacity grows with every participant, at the cost of harder search, trust, and consistency. Hybrid designs, now the norm, keep a small coordinating service for metadata or membership and push bulk work to the edges. Most large storage and compute systems follow this pattern.

PaperStoica et al., "Chord: A Scalable Peer-to-Peer Lookup Service," SIGCOMM 2001

How nodes talk

Nodes share nothing but the network, so every interaction is a message. Four patterns cover most systems, differing in whether sender and receiver must be active at the same time and whether they know each other.

PapersBirrell & Nelson, "Implementing Remote Procedure Calls," ACM TOCS 2(1), 1984 · Eugster et al., "The Many Faces of Publish/Subscribe," ACM Computing Surveys 35(2), 2003

Eight fallacies

Engineers new to distributed systems tend to make the same false assumptions, catalogued at Sun Microsystems in the 1990s. Each one, believed, produces a specific class of bug.

1. The network is reliablePackets drop; code needs retries and idempotent operations.
2. Latency is zeroChatty protocols collapse across regions.
3. Bandwidth is infiniteLarge payloads saturate links and starve others.
4. The network is secureEvery hop needs authentication and encryption.
5. Topology doesn't changeHosts move and routes shift; hard-coded addresses break.
6. There is one administratorPolicies, versions, and upgrades conflict.
7. Transport cost is zeroSerialization and data transfer cost CPU and money.
8. The network is homogeneousMixed hardware and protocols need interoperability.

TutorialRotem-Gal-Oz, "Fallacies of Distributed Computing Explained"

The CAP trade-off

Three properties are desirable in any replicated data store:

• Consistency (C): every read sees the most recent write, as if there were one copy.
• Availability (A): every request to a working node gets a response.
• Partition tolerance (P): the system keeps operating when the network splits nodes into groups that cannot talk.

The CAP theorem, conjectured by Brewer and proved by Gilbert and Lynch, says that during a partition you cannot have both C and A. Since real networks do partition, the practical choice is what to give up when they do.

Two refinements matter. First, the choice is not permanent or global; a system can choose differently per operation or per data type. Second, even with no partition, stronger consistency costs latency because replicas must coordinate. The PACELC formulation captures this: under Partition choose A or C, Else choose Latency or Consistency.

PapersGilbert & Lynch, "Brewer's Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services," SIGACT News 33(2), 2002 · Brewer, "CAP Twelve Years Later," IEEE Computer 45(2), 2012 · Abadi, "Consistency Tradeoffs in Modern Distributed Database System Design," IEEE Computer 45(2), 2012
ExploreJepsen consistency models map

In practice

Three well-documented systems show these trade-offs made on purpose.

PaperMcSherry, Isard & Murray, "Scalability! But at what COST?" HotOS 2015

Tools and reading