Computer Science › Software + Distributed Computing
Consensus when message delays are bounded: leader election by rounds, what a crash costs, the f+1 rounds lower bound, and why this simple world is the baseline asynchronous protocols are measured against.
Total-order broadcast as the abstraction replicated systems actually need, how it reduces to a sequence of consensus instances, and the conditions under which the two problems are equivalent.
From single-decree Paxos to a replicated log: a stable leader, skipping phase 1 for later slots, filling gaps, and what the existing Paxos lesson left out on liveness.
Fast Paxos and its fast path that skips the leader, with the larger quorums it pays for, then Flexible Paxos, which shows that only phase 1 and phase 2 quorums must intersect.
Changing the set of replicas without losing safety: configuration entries in the log, Raft's joint consensus and single-server changes, and the disjoint-majorities failure they prevent.
Unreliable failure detectors as defined by Chandra and Toueg, their completeness and accuracy classes, the weakest detector for consensus, and heartbeat-based and phi-accrual detectors in practice.
Group membership as a sequence of agreed views, view-synchronous communication, and how the virtual synchrony model relates to consensus-based replication.
Causal consistency as a model between sequential consistency and PRAM, potential causality from happens-before, tracking dependencies with vector clocks and explicit metadata, and what the availability result usually cited for it actually proves.
Extending causal consistency to read-only and write transactions, causal snapshots, and what geo-replicated systems built on this model give up.
The classic design space of database replication, eager versus lazy and primary-copy versus update-everywhere, and certification-based replication built on total-order broadcast.
Epidemic algorithms from the Xerox PARC work: push, pull, and push-pull gossip, how quickly a rumor spreads, and how anti-entropy and rumor mongering differ.
Unstructured overlays: flooding and its cost, super-peers as a compromise, and how BitTorrent's tit-for-tat and rarest-first change the problem from search to dissemination.
Chord's identifier ring, successors and finger tables, why a lookup takes a logarithmic number of hops, how stabilization repairs the ring, and where the original protocol fails under failures.
Two DHTs that route by shared identifier digits or XOR distance: Kademlia's k-buckets and Pastry's routing table, and why parallel lookups and locality matter in practice.
Building publish-subscribe on a structured overlay: topic-based dissemination trees as in Scribe, and how the design compares with a centralized broker.
The shared log as a primitive: CORFU's sequencer and client-driven replication over flash, Tango's replicated data structures on top of it, and vCorfu's materialized streams.
Two ways past a single sequencer: FuzzyLog relaxes the total order into a partial order across colors, and Scalog replicates records first and orders them afterwards.
Using a shared log as the state substrate of serverless functions: Boki's log-based abstractions for workflows and transactions, and FlexLog's take on the same problem.
Reducing the ordering latency of shared logs: LazyLog acknowledges appends before binding their position, which runs in the background and is enforced before a position can be read, and SpecLog lets consumers compute on a speculative order while external output waits for confirmation.
Calvin's inversion of the usual order: agree on a global sequence of transactions first, then execute them deterministically at every replica, which removes two-phase commit from the path.
Moving ordering into the network: NOPaxos's ordered unreliable multicast, Eris's in-network concurrency control for transactions, and Hydra's approach to network ordering without a serialization point.
Saturn's separation of data from causal metadata: a tree of serializers that propagates a small label, and the trade-off between visibility latency and throughput.
Given a concrete workload, choose among consensus, certification, causal, shared-log, deterministic, and network-ordered designs, and defend the choice against its failure modes and costs.
Part of the Computer Science curriculum.
Consensus when message delays are bounded: leader election by rounds, what a crash costs, the f+1 rounds lower bound, and why this simple world is the baseline asynchronous protocols are measured against.
Total-order broadcast as the abstraction replicated systems actually need, how it reduces to a sequence of consensus instances, and the conditions under which the two problems are equivalent.
From single-decree Paxos to a replicated log: a stable leader, skipping phase 1 for later slots, filling gaps, and what the existing Paxos lesson left out on liveness.
Fast Paxos and its fast path that skips the leader, with the larger quorums it pays for, then Flexible Paxos, which shows that only phase 1 and phase 2 quorums must intersect.
Changing the set of replicas without losing safety: configuration entries in the log, Raft's joint consensus and single-server changes, and the disjoint-majorities failure they prevent.
Unreliable failure detectors as defined by Chandra and Toueg, their completeness and accuracy classes, the weakest detector for consensus, and heartbeat-based and phi-accrual detectors in practice.
Group membership as a sequence of agreed views, view-synchronous communication, and how the virtual synchrony model relates to consensus-based replication.
Causal consistency as a model between sequential consistency and PRAM, potential causality from happens-before, tracking dependencies with vector clocks and explicit metadata, and what the availability result usually cited for it actually proves.
Extending causal consistency to read-only and write transactions, causal snapshots, and what geo-replicated systems built on this model give up.
The classic design space of database replication, eager versus lazy and primary-copy versus update-everywhere, and certification-based replication built on total-order broadcast.
Epidemic algorithms from the Xerox PARC work: push, pull, and push-pull gossip, how quickly a rumor spreads, and how anti-entropy and rumor mongering differ.
Unstructured overlays: flooding and its cost, super-peers as a compromise, and how BitTorrent's tit-for-tat and rarest-first change the problem from search to dissemination.
Chord's identifier ring, successors and finger tables, why a lookup takes a logarithmic number of hops, how stabilization repairs the ring, and where the original protocol fails under failures.
Two DHTs that route by shared identifier digits or XOR distance: Kademlia's k-buckets and Pastry's routing table, and why parallel lookups and locality matter in practice.
Building publish-subscribe on a structured overlay: topic-based dissemination trees as in Scribe, and how the design compares with a centralized broker.
The shared log as a primitive: CORFU's sequencer and client-driven replication over flash, Tango's replicated data structures on top of it, and vCorfu's materialized streams.
Two ways past a single sequencer: FuzzyLog relaxes the total order into a partial order across colors, and Scalog replicates records first and orders them afterwards.
Using a shared log as the state substrate of serverless functions: Boki's log-based abstractions for workflows and transactions, and FlexLog's take on the same problem.
Reducing the ordering latency of shared logs: LazyLog acknowledges appends before binding their position, which runs in the background and is enforced before a position can be read, and SpecLog lets consumers compute on a speculative order while external output waits for confirmation.
Calvin's inversion of the usual order: agree on a global sequence of transactions first, then execute them deterministically at every replica, which removes two-phase commit from the path.
Moving ordering into the network: NOPaxos's ordered unreliable multicast, Eris's in-network concurrency control for transactions, and Hydra's approach to network ordering without a serialization point.
Saturn's separation of data from causal metadata: a tree of serializers that propagates a small label, and the trade-off between visibility latency and throughput.
Given a concrete workload, choose among consensus, certification, causal, shared-log, deterministic, and network-ordered designs, and defend the choice against its failure modes and costs.