Distributed Systems §
Distributed systems study how to coordinate computation across multiple machines that communicate over a network. They are relevant whenever a single machine cannot provide the required throughput, availability, or data capacity.
Utility §
- It enables horizontal scaling: adding machines to increase throughput.
- It provides fault tolerance: the system survives individual node failures.
- It coordinates state: multiple nodes agree on a consistent view of the data.
Details
Distributed systems sit at the rightmost end of the computation pipeline: they take the executable programs running on individual machines (produced by the hardware and OS layers) and coordinate them into a single logical system. The fundamental challenge is that the network is unreliable: messages are lost, delayed, or duplicated; nodes crash; and the network can partition. The design space is governed by the CAP theorem (a partitioned system must choose between consistency and availability) and the FLP impossibility (no deterministic consensus algorithm can tolerate even one crash in an asynchronous system).
History §
- 1977: Lamport publishes “Time, Clocks, and the Ordering of Events,” founding distributed systems theory.
- 1985: FLP impossibility theorem: no deterministic consensus in an asynchronous system with one crash.
- 1990: Paxos (Lamport) and 2PC (Garcia-Molina) provide consensus and atomic commit.
Classes §
| Page | Core object | Key metric | Boundary |
|---|---|---|---|
| Concurrency | Threads, processes, locks, message passing | Throughput, contention, deadlock freedom | How to coordinate execution within a single machine; does not model the network |
| Asynchrony | Event loop, async/await, non-blocking I/O | Connections per thread, I/O multiplexing ratio | How a single thread multiplexes many I/O operations; sub-topic of Concurrency |
| Message passing | Messages, channels, queues, RPC, publish/subscribe | Latency, throughput, ordering guarantees | How concurrent activities exchange data asynchronously; does not model how messages are physically transmitted |
| Parallelism | Threads, processes, SIMD, data-parallel execution | Speedup, efficiency, Amdahl's law | How to split work across execution units on one machine; does not model coordination across machines |
| Networks | Protocols, sockets, routing, TLS | Latency, throughput, reliability | How messages are transmitted between machines; does not model the application logic |
| Queueing and Latency | Queues, Little's law, tail latency, backpressure, rate limiting | Throughput, tail latency, saturation threshold | How load translates into latency and when a system saturates; does not model how to add capacity |
| Scaling Strategies | Load balancers, caching, CDNs, sharding, autoscaling | Throughput, cost per request | How to add capacity (vertical or horizontal); does not model fault tolerance or consistency |
| Network partitions | FLP, CAP, consensus (Paxos, Raft), consistency models | Availability, consistency, partition tolerance | How to agree on state when the network partitions; does not model the physical network or the application |
| Robustness | Replication, quorum, failover, RPO/RTO, circuit breakers | RPO, RTO, availability | How to survive failures; does not model the consensus protocol or the network |
| Adversarial failure | Byzantine faults, PBFT, Sybil attacks | Byzantine tolerance (3f+1), identity cost | How to survive malicious nodes; does not model crash faults or the network |
Authoritative sources