Distributed Systems
A single database server has a big advantage. It has one clock, one memory, and one disk. When two writes happen, the server decides which came first. When a transaction commits, the server writes the commit record in one place. When a crash happens, the whole machine stops together, so you know what state you are in.
Distributed systems give up that advantage. A distributed system is a set of machines that cooperate over a network to act as one service. Each machine has its own memory and clock, and the network between them can delay, reorder, or drop messages. A machine that stops answering might have crashed, or it might just be slow, and from the outside you cannot tell which. Databases spread across machines need answers to five questions. How does one machine notice that another is gone? How do copies of the same data stay consistent? How do replicas catch up after they fall behind? How does a transaction touching several machines commit everywhere or nowhere? How do machines agree on a value at all when some of them fail? The five sections below take these questions in order, and each one builds on the answer before it.
Failure Detection
Every other mechanism in a distributed system needs to know when a node has stopped. A replica that takes writes while its partner is dead will drift apart from it. A commit protocol that waits forever for a dead participant will hang. So the first question is how a node decides that another node has failed.
The usual tool is the heartbeat: each node sends a small "I am alive" message to its peers at a fixed interval. If a node hears nothing from a peer for longer than a timeout, it marks that peer as suspected. The word "suspected" matters. A failure detector never knows a node is dead. It only sees silence, and silence can come from a crash, a long garbage-collection pause, or a congested network link.
That gives you a trade-off that is at the heart of this topic. A short timeout detects real crashes quickly, but it also flags healthy nodes that were merely slow; those are false positives. A long timeout avoids false alarms but leaves a dead node in service for longer, which is the detection delay. Picture a monitoring tool that pages you after 2 seconds of silence. It will catch a crashed server fast, and it will also wake you up every time a backup job spikes the CPU for 3 seconds. Setting the timeout is always a choice about which mistake you would rather make.
Replication and Consistency
Replicas are extra copies of the same data on different machines. You keep them for three reasons: if one machine dies, another still has the data; several machines can serve reads, so the system handles more load; and copies placed near users cut response time. The hard part is not making copies. The hard part is deciding what a client is allowed to observe when copies disagree for a moment.
The CAP theorem is the first and most famous framing of that problem. It says that when a network partition splits the replicas into groups that cannot talk to each other, a system must choose between consistency, where every read sees the latest write, and availability, where every request gets a response. CAP is useful because it names a real trade-off. It is not sufficient on its own, because it says nothing about the normal case when there is no partition, and nothing about latency. A system can be fast and consistent most of the time, and the theorem does not describe how it behaves in that case.
Beyond CAP sits a family of consistency models, which are precise contracts about the order in which a client sees operations. Some models promise only that replicas converge eventually. Others promise that all clients see one global order of writes. The strongest common contract is linearizability, which says each operation appears to take effect at a single instant between its start and its end. Linearizability and strict consistency sound alike but differ in how they define that instant, and the difference matters when you build a system on top of them. The last part of this layer is operational: deciding which replicas exist, which node is authoritative for which key, and what happens when a replica is added or removed.
Anti-entropy and Dissemination
Even a well-designed replicated system will fall out of sync. A message gets lost, a node restarts after missing a few updates, or a disk silently corrupts a block. Anti-entropy is the background process that finds these differences and repairs them. Dissemination is the related problem of spreading new updates across the whole cluster quickly without flooding the network.
Comparing two large datasets line by line is slow, so repair protocols compare summaries instead. A Merkle tree is a tree of hashes: each leaf hashes a small range of keys, and each parent hashes its children. Two replicas compare their root hashes first. If the roots match, they are identical and no data moves. If they differ, they descend only into the subtrees whose hashes differ, so the amount of data exchanged tracks the amount of divergence rather than the total size. Bitmap version vectors solve a neighbouring problem: they record, for each replica, which updates it has seen, so two replicas can tell whether one has updates the other is missing, and can tell concurrent updates apart from ordered ones.
Gossip protocols handle dissemination. Each node periodically picks a random peer and exchanges state with it. Information spreads the way a rumour does, with each round roughly doubling the number of informed nodes, so a cluster of $n$ nodes is usually covered in about $O(\log n)$ rounds. Gossip needs no central coordinator and tolerates failures well. One practical question remains: a node that knows only a few peers cannot pick from all of them. That is why gossip variants use partial views, small random subsets of the membership, and hybrid gossip, which combines gossip with a more deterministic push when speed matters. These ideas matter because they show that you can keep a large cluster synchronised without anyone knowing the whole cluster.
Distributed Transactions
A transaction is a group of reads and writes that must succeed or fail as a unit. On one machine, the database handles this with a log and locks. When the transaction spans several partitions, each on a different machine, no single machine can decide alone. Every participant has to agree that the transaction commits, or none of them may commit it. The guarantee that matters is atomicity: either all of a transaction's effects appear, or none do. Isolation is the related guarantee that concurrent transactions do not see each other's half-finished work.
The classic protocol is two-phase commit, usually called 2PC. A coordinator asks every participant to prepare, meaning each one writes its changes durably and promises it can commit. If all of them vote yes, the coordinator writes a commit decision and tells everyone to commit. If any participant votes no, everyone aborts. The protocol is simple and correct, but it has a sharp edge: if the coordinator crashes after participants have prepared, those participants must wait, holding their locks, until the coordinator returns. That blocking behaviour is the main cost of 2PC.
Two systems show different ways to live with that cost. Calvin avoids the commit protocol across partitions by agreeing on the order of all transactions in advance, so every partition executes the same deterministic sequence and reaches the same result without a vote. Spanner runs 2PC across groups of machines where each group is itself replicated with consensus, so a participant does not disappear when one machine fails. Spanner also depends on tightly bounded clock uncertainty to assign timestamps that respect real time. This is the core chapter for understanding cross-node commit, and the Spanner paper is worth reading in full.
Consensus
Consensus is the problem of getting a set of nodes to agree on one value, even when some of them crash and messages are delayed or lost. It is the foundation under replicated logs, leader selection, and commit decisions that must survive failures. A famous impossibility result shows that in a fully asynchronous system, where delays have no upper bound, no algorithm can guarantee consensus with even one crash. Real systems get around this with timeouts, which brings back the failure detection trade-off from the first section, and with a majority rule: a value is decided once a quorum, a majority of the nodes, has accepted it. Two majorities always overlap, so they cannot decide two different values.
Paxos is the original and most studied protocol. Its roles are proposers, which push values, and acceptors, which vote on them, and it runs in phases that use quorums to keep decisions consistent. Paxos is hard to implement correctly, and it comes in variants (Multi-Paxos, Fast Paxos, and others) that trade message counts and leader stability against each other. Those variants are a good map of how much agreement different environments actually need. Raft solves the same problem with a leader that orders a replicated log, which is easier to explain and implement. Read the Paxos and Raft papers directly, since they are the primary sources.
Everything so far assumes nodes fail by stopping. Byzantine fault tolerance handles nodes that lie, send conflicting messages, or behave arbitrarily. Tolerating $f$ such nodes requires at least $3f + 1$ total nodes, which is a much higher price than the crash-only case. You pay that cost mainly when machines do not trust each other, such as in open networks.
AI-generated study article from SophistAI. Sign up free to study it with an AI tutor.