Distributed Systems

Defines logical clocks and the happens-before relation for ordering events without synchronised time.

The single most-cited distributed-systems paper. Read it first; everything else assumes it.

Basic concurrency

You don't need synchronised clocks — only a partial ordering of events.

Formalises consensus when some nodes can lie or behave arbitrarily, and proves bounds on tolerance.

Defines the worst-case adversary model that drives blockchain and high-assurance systems.

Lamport clocks, basic algorithms

You can survive arbitrary failures iff fewer than one-third of nodes are faulty.

Argues that functions like reliability and security belong at endpoints, not inside the network.

A foundational systems-design principle, far beyond just distributed systems.

TCP/IP basics

Push correctness to the edges; let the middle stay simple.

Proves that no deterministic asynchronous algorithm can guarantee consensus if even one process can crash.

The negative result every consensus designer must know — sets the boundary for what's possible.

Distributed algorithms basics, asynchronous models

In a fully asynchronous network, you must give up either fault-tolerance or termination.

A consensus protocol that tolerates crashes via majority quorums and ordered ballots.

The bedrock consensus protocol — every modern system either runs Paxos or a Paxos cousin.

FLP, majority voting

Majorities of replicas can agree on a value despite asynchronous networks and crash failures.

A consensus protocol designed for understandability with explicit leader election and log replication.

Replaced Paxos in most production systems written after 2014. Easier to read, easier to implement.

Paxos

A clearer protocol with the same guarantees is itself a research contribution.

Brewer revisits his CAP conjecture and clarifies the actual tradeoffs designers face during partitions.

Cleaner than the original CAP conjecture; corrects common misreadings.

Distributed systems basics

CAP is about what you do during partitions, not a forced binary choice.

A taxonomy of conflict-free replicated data types that converge without coordination.

The cleanest reference on the data-type primitives behind eventually-consistent systems and collaborative editors.

Distributed systems basics, lattice theory

Pick data types that mathematically can't conflict, and you can drop coordination.

A petabyte-scale distributed file system optimised for large appends and commodity hardware failures.

The conceptual ancestor of HDFS and the storage layer of an entire generation of big-data stacks.

File system basics

Design for failure as the common case, not the exception.

A sparse, distributed, persistent multi-dimensional sorted map built on GFS and Chubby.

The conceptual ancestor of HBase, Cassandra, and most modern wide-column NoSQL stores.

GFS, LSM-trees

Sorted-string tables and a log-structured merge engine scale to petabytes.

A masterless, eventually-consistent KV store using consistent hashing, vector clocks, and quorums.

The conceptual root of Cassandra, Riak, and the AP-side of NoSQL.

Consistent hashing, vector clocks

Tuneable consistency on writes and reads is a more useful knob than a single consistency level.

A wide-column store mixing Bigtable's data model with Dynamo's eventually-consistent ring.

The pragmatic distillation of two papers everyone reads — Bigtable plus Dynamo.

Bigtable, Dynamo

You can fuse two seemingly opposing designs if you pick the right pieces of each.

A coarse-grained distributed lock service implemented over Paxos for Google's coordination needs.

Codifies what a coordination primitive should look like — read this before ZooKeeper.

Paxos

A reliable lock service is itself a foundational distributed primitive.

A high-throughput coordination service exposing a hierarchical filesystem-like API over a replicated log.

The most-deployed coordination service of the last decade; understanding it sharpens your distributed-systems intuition.

Chubby, Paxos

Expose coordination through familiar primitives (files, watches) and people will actually use it.

A two-stage programming model with automatic parallelisation, fault tolerance, and data locality.

The paper that defined "big data" and seeded Hadoop, Spark, and the modern analytics stack.

Functional programming basics

Reduce a complex distributed problem to two simple functions, and the framework handles the rest.

An in-memory abstraction that recomputes lost partitions from lineage rather than checkpointing.

The paper that displaced MapReduce; required reading for anyone touching analytics infrastructure.

MapReduce, functional programming

Logging deterministic transformations is enough to reconstruct lost state.

A unified runtime for streaming and batch via consistent checkpointing and asynchronous barrier snapshots.

Best modern reference on what stream processing actually requires.

Spark, basic stream processing

Batch is just a special case of streaming with bounded data.

A two-level scheduler that offers resources to higher-level frameworks rather than scheduling tasks itself.

The conceptual ancestor of Kubernetes; clarifies the design space of cluster schedulers.

Distributed systems basics

Push policy decisions up to the framework; keep the cluster manager mechanism-only.

A globally-distributed SQL database providing externally-consistent transactions via TrueTime.

The first system to make globally-consistent transactions practical — a watershed in DB design.

Bigtable, Paxos, clock synchronisation

Tight clock bounds, plus a wait, give you serialisable distributed transactions.

A deterministic database that orders all transactions globally before executing them in parallel.

A fundamentally different approach to transactions than 2PC — worth reading for the contrast.

Spanner, 2PC

If you agree on the order of transactions first, you can run them without coordinating during execution.

A distributed, partitioned, replicated commit log designed as the central nervous system of an org's data.

The paper that re-popularised the log as a foundational data abstraction.

Distributed systems basics

A simple, durable, ordered append-only log is the right primitive for moving data around.

A decade of lessons from running Google's internal cluster manager — the predecessor to Kubernetes.

The most candid production-systems paper of the 2010s; required reading before designing any scheduler.

Mesos

Most of the work in cluster management is operational, not algorithmic.

A low-overhead, always-on tracing system that propagates span identifiers across RPC boundaries.

Sets the design template for OpenTelemetry, Jaeger, and every modern tracing system.

RPC basics

Sample your traces, propagate context, and you can debug anything.

A measured critique of FaaS that catalogues what serverless gets right and where it falls short.

A useful counterweight to vendor hype; sharpens your sense of what cloud abstractions should do.

Distributed systems basics, cloud architecture

Stateless functions are easy; the hard problems are state, coordination, and shared memory.

A coordination-free, multi-master KV store that scales linearly across cores, machines, and regions.

A clean modern read on what coordination-free design buys you and where it bites.

Dynamo, CRDTs

Lattice-based replication can give you both speed and consistency knobs.

A specification language and model checker for concurrent and distributed algorithms, with worked examples.

Less a paper than a discipline — distributed bugs become tractable when you can specify them.

Discrete math, first-order logic

Specifying a system precisely catches bugs no test ever will.