Distributed systems are programmed by combining a small set of foundational algorithms. The same primitives — logical clocks, gossip, quorum reads/writes, replication — show up across Cassandra, Kafka, etcd, CockroachDB, S3 internals. Knowing them by name lets you read papers and source code; knowing why each one exists lets you design.
Wall-clock time across machines isn't reliable enough to order events. NTP gets you milliseconds; with clock skew, two events on different machines might appear out of order. Logical clocks provide order without reliance on wall time.
Each process maintains a counter. On any local event, increment. On send, attach the counter. On receive, set local counter to max(local, received) + 1.
Property: if event A causes event B (causally), then lamport(A) < lamport(B). The reverse isn't true — concurrent events can have arbitrarily ordered Lamport timestamps.
Used for: total ordering of events when you don't need to detect concurrency.
Each process maintains a vector indexed by all processes. Increment own entry on each event. On send, attach. On receive, take element-wise max, then increment own entry.
Property: distinguishes "A happened before B" from "A and B are concurrent." Two timestamps are concurrent if neither is component-wise ≤ the other.
Used for: detecting concurrent updates (Dynamo, Riak), causal consistency systems.
Cost: vector size grows with the number of processes. For very large or dynamic process sets, dotted version vectors and similar refinements help.
Combines wall clock with logical counter. Approximates wall-clock ordering when clocks are reasonably synchronised; falls back to logical when they diverge.
Used in CockroachDB, MongoDB. Practical compromise — get most of NTP's intuitive ordering with the safety of logical clocks under skew.
Google has tightly-synchronised clocks (GPS + atomic) with bounded uncertainty intervals. They use this to provide external consistency — actual real-time ordering. Most systems can't afford the hardware to do this.
Replication with N replicas. Reads see at least R replicas; writes commit to at least W replicas. Consistency follows from R + W > N (the read quorum and write quorum overlap, so reads see at least one replica that has the latest write).
Common settings:
N=3, R=2, W=2 — typical Cassandra / DynamoDB. One replica failure doesn't stop the system; reads and writes are quorum-consistent.N=3, R=1, W=3 — fast reads (any replica); slow writes (all). Used for read-heavy workloads where staleness matters.N=5, R=3, W=3 — tolerates two failures; uses majority quorum (Raft-style).Quorums are simpler than consensus algorithms but provide weaker guarantees (no linearizability without more machinery). For many workloads, "eventually consistent with quorum reads" is sufficient.
Each node periodically picks a random peer; exchanges some state with it. State propagates exponentially across the cluster.
Used for:
Cassandra, Consul, Riak use gossip extensively.
Properties:
O(log N) rounds for full propagation.Cost: noisy if poorly tuned (excessive bandwidth); slow to converge for very large clusters.
When replicas drift apart, anti-entropy reconciles them. Periodic; checks replica states against each other; copies missing or newer data.
Without anti-entropy, replicas drift permanently after any write loss. Don't skip.
Strong agreement on a value among replicas in the presence of failures. Paxos, Raft, Zab are the proven algorithms.
When you need consensus:
When you don't:
Consensus is expensive: each operation requires majority round-trips. Reaching for it when eventual consistency would do is a common over-engineering.
See PaxosAndRaft for the algorithms.
Coordinator asks all participants "can you commit"; if all say yes, tells them to commit; if any say no, tells them to abort.
Limitations:
Use in single-datacenter, tight-latency environments. Don't use across services in microservice architectures — saga (compensating transactions) wins.
Three-phase commit (3PC) tries to eliminate blocking but assumes synchronous networks; rarely used in practice because the assumption fails.
Data structures designed so that concurrent updates can be merged automatically without a coordinator.
Property: any two replicas, given the same set of updates, end up at the same state regardless of order or duplicates. No locking; no coordinator.
Cost: state grows over time without garbage collection; some types are storage-heavy.
See CrdtDataStructures for depth.
How do you tell when a node is dead? Three approaches:
The CAP-theorem corollary: in an asynchronous network, you cannot reliably distinguish "dead" from "very slow." All failure detection is heuristic; live with false positives.
A way to map keys to nodes such that adding or removing a node only moves 1/N of the keys, not all of them.
Hash both keys and nodes onto a ring (e.g., a 32-bit space). A key is owned by the next node clockwise on the ring.
Used in Memcached, Cassandra, DynamoDB, web caching layers. Standard technique for partitioning.
Variants:
See ConsistentHashing.
For "does any node have this key" without asking all of them: each node maintains a Bloom filter of its keys; share filters via gossip; query the union.
Used in some distributed caches and for routing in P2P systems.
Cassandra combines most of the above:
R and W.Each component does one job; the composition produces a high-availability eventually-consistent distributed database. Reading the Cassandra source is one of the better ways to see distributed-systems algorithms in production.