Principles of Distributed Computing (Wattenhofer)

Roger Wattenhofer‘s lecture notes for the ETH Zürich course, Spring 2016 — 321 pages, 22 chapters, freely published by the Distributed Computing group. T1: a university course text by the field’s professor, with theorems and proofs rather than assertions.

It closes this spoke’s #1 growth edge — “the distributed-consistency substance… cross-shard transactions, consistency models, replication and consensus” — from the theory side rather than the engine side the edge had asked for.

What this spoke takes from it

Seven chapters (roughly 100 of the 321 pages) are this spoke’s subject:

• 15 Fault-Tolerance & Paxos — client/server failure models, then Paxos derived step by step.
• 16 Consensus — the definition, the impossibility proof, then randomized consensus and shared coins as the way around it.
• 17 Byzantine Agreement — arbitrary-failure model, the resilience bound, the King algorithm, a lower bound on rounds, asynchronous agreement.
• 18 Authenticated Agreement — what signatures buy, and Zyzzyva.
• 19 Quorum Systems — load and work, grid quorums, fault tolerance, byzantine quorums.
• 20 Eventual Consistency & Bitcoin — CAP, Bitcoin as a worked example of eventual consistency, weak-consistency definitions.
• 21 Distributed Storage — consistent hashing, hypercubic networks, DHTs and churn.

The two results a database reader should carry are on consensus and consistency-models.

The impossibility result, stated exactly (Theorem 16.14): “There is no deterministic algorithm which always achieves consensus in the asynchronous model, with f > 0.” Not “consensus is hard” — no deterministic algorithm, ever, with one crash-faulty node and no timing assumptions. Every consensus system in production is a way of paying for an assumption that dodges it.

The byzantine bound: arbitrary-failure agreement needs f < n/3. That is why byzantine-tolerant systems quote three-times-plus-one node counts.

On CAP, the notes give the provenance the trade literature usually skips: introduced by Fox and Brewer (1999), popularised by Brewer’s 2000 talk, and proven by Gilbert and Lynch (2002) for the asynchronous model — who also showed the consistency requirement can be relaxed in a partially synchronous system to get availability and partition tolerance. The theorem is a real theorem with a model attached, not a slogan about picking two of three.

What this spoke does not take from it

The other fifteen chapters are a general distributed-computing course and are out of this spoke’s scope: vertex colouring, tree algorithms and MST, distributed sorting and counting networks, maximal independent sets, locality lower bounds, social networks and small-world graphs, synchronizers and clock synchronisation, communication complexity, wireless protocols, self-stabilisation, labeling schemes, and game theory.

That is most of the book, and it is recorded here rather than paged. Worth being plain about the consequence: this is a source whose centre of gravity sits outside the spoke that holds it. If more distributed-systems theory arrives — the locality/lower-bound material, or self-stabilisation — a distributed-systems-theory cluster is the natural home and this routing should be revisited rather than defended.

Why the theory earns a place in a database wiki

The spoke’s founding axis is how far one logical database stretches, from turso in-process to planetscale-768-servers across 768 machines. Everything past the embedded pole is a distributed system, and until now the corpus described mechanisms — hash routing, proxy aggregation, scatter-gather — without the results that say which of them are possible.

FLP is why a sharded store cannot simply “agree” on a commit without timeouts or randomisation. The byzantine bound is why replica counts look the way they do. CAP with its model attached is why local-first designs choose merge semantics instead of coordination. The mechanisms this spoke already holds now have the constraints they were built against.

Related

consensus · consistency-models · database-sharding · cross-shard-queries · online-transaction-processing · rethinking-data-client-event-sourcing · vitess · roger-wattenhofer · eth-zurich · synthesis