Distributed systems

Leader-based consensus on a replicated log; one leader per term, majority commit; the default for a strongly consistent replicated state machine.

Paxos run once per log slot with a stable leader that skips phase 1; the foundation of Chubby, Spanner and much production consensus.

Periodically save the state a log has produced at index i so the log prefix can be deleted; recovery and catch-up become load snapshot plus replay suffix.

Replicas in a line: writes enter at the head and commit at the tail, reads hit the tail; f+1 nodes tolerate f failures.

Leaderless replication: write to W of N replicas, read from R; overlap (R + W > N) makes reads see the latest completed write.

Data types whose replicas accept writes independently and always converge by merging, with no coordination: counters, sets, maps, registers, text.

One node orders all writes and ships them to standbys; the acknowledgement rule (none, one, all) sets what a crash loses, and an external arbiter decides who takes over.

Replicas compare hash trees of a key range, descend only into differing subtrees and stream just those ranges, healing silent divergence in the background.

Park a write meant for a down replica as a tagged hint on a healthy node, replay it when the replica returns, and count it toward the write quorum only if availability matters more than consistency.

One integer per process, max-plus-one on receive; gives a total order consistent with causality using 8 bytes per timestamp.

One counter per node; comparing two vectors tells whether events are ordered or concurrent, which is exactly what conflict detection needs.

A 64-bit timestamp that tracks wall-clock time but never goes backwards and respects causality; the default timestamp for MVCC databases without atomic clocks.

Estimate a clock's offset from four timestamps, filter out queueing noise, and steer the clock smoothly; NTP gets about a millisecond, PTP with hardware timestamps under a microsecond.

Mint unique, roughly time-sorted IDs on many nodes with no per-ID coordination: Snowflake (time, worker, sequence) or UUIDv7 (time, random).

Hash nodes and keys onto a ring; each key belongs to the next node clockwise, so membership changes move only about 1/n of keys.

Score every node with hash(key, node) and pick the highest: minimal key movement and exact weights without a ring, at O(n) per lookup.

Five lines, zero memory, near-perfect balance: maps a 64-bit key to one of n numbered buckets, moving only 1/(n+1) of keys when n grows.

Cut the sorted key space into contiguous half-open ranges kept in a boundary map; split hot or big ranges, merge small ones, move ranges between nodes.

Split or move a shard while it serves traffic by copying a snapshot, replaying changes until the lag is tiny, then flipping a versioned routing table.

Send a query only to shards that can match, merge their small partial results, and bound the wait for stragglers.

Each node probes one random peer per period, asks k others on timeout, and piggybacks membership updates; constant load per node at any cluster size.

Instead of a fixed heartbeat timeout, output a continuous suspicion level φ from the observed heartbeat interval distribution; adapts to each link's jitter.

Heartbeats refresh per-connection TTLs; a user is online while any connection lives, with a grace period that hides reconnect flaps.

Atomic commit across shards: participants durably vote yes, then the coordinator logs and broadcasts one decision; blocks if the coordinator is lost.

A lock that expires on its own: bounded-time ownership that survives crashes and partitions, given bounded clock drift and fencing tokens on writes.

A number that grows with every lock grant and is checked by the protected resource, so a paused ex-holder's late write is rejected.

Split a cross-service operation into local transactions, each paired with an undo; on failure run the undos in reverse, or retry forward.

Write the event as a row in the same local transaction as the state change; a relay publishes it later at-least-once, so state and events never diverge.

A control plane pushes versioned resource changes over long-lived streams; each node validates, ACKs or NACKs and keeps its last good copy, so a bad change stops at a canary.

Declare the target in a store; controllers repeatedly diff actual against desired from full state and apply idempotent fixes, so missed events only delay convergence.

A store numbers every write; clients list at revision R, then watch from R+1 and receive an ordered change stream with no gap, no duplicate, and a resume point.

A topic split into replicated append-only partitions: key hash keeps per-key order, offsets give position, and a high watermark limits readers to fully replicated records.

Split an append-only log into files named by their first offset, write only the newest, and find any record by binary search plus a sparse index.

Each consumer group stores one integer per partition, the next position to read, so a restarted consumer resumes where it left off with at-least-once delivery.

Persisted tasks that workers lease for a visibility timeout, ack on success and retry with backoff; at-least-once execution that survives worker and queue crashes.

A side queue for messages that keep failing: after N delivery attempts or a permanent error, park them with the reason so the main queue keeps moving.

Keep the ids of recently accepted events for a time window and drop repeats; memory stays bounded by rotating time buckets instead of per-entry timers.

Deliver one published message to every subscriber of a topic by sharing one encoded payload and giving each connection a bounded queue with an explicit slow-consumer policy.

Append each new item id to every follower's precomputed, capped list so a read is one fetch; pull the few huge authors at read time instead.

A per-stream counter on every message lets the receiver detect loss, duplicates and reordering, ack cheaply and resume after reconnect with "send from N".

Group events by event-time window per key, keep one partial aggregate per slice, and emit a window when the watermark passes its end.

Run a graph of dependent tasks by releasing each one when its inputs are done, longest chain first, and skip any task whose input hashes are unchanged.

Ordinary code made crash-proof by logging every side-effect result and replaying the code from that log; activities run at least once, workflow logic must be deterministic.

The client keeps one opaque token; each pull returns only the changes after it plus the next token, so sync cost scales with what changed, not with the dataset.

Apply actions locally at once and queue them durably; on reconnect replay the queue idempotently, then re-apply unconfirmed ones on the server state.

Give every list item a sortable string key and generate a new key strictly between its neighbours, so a move or insert writes one row.

Merge two descendants against their common ancestor: take whichever side changed, report a conflict only where both changed the same spot differently.

Run the whole system in one thread under a seeded scheduler with simulated network, disk and clock, so every failure replays from its seed.

Send requests on a fixed or random schedule regardless of replies, and time each from its intended send time, so stalls show up in the tail.

Each rank stores its block plus a border copy of its neighbours' edge cells, refreshed by small messages every step; communication scales with block surface, not volume.

A server-side turn timer that credits back each move's measured network lag, capped per move and by a quota that refills a fixed amount per move.