Lectures

The following topics will be presented over the course of the semester. Each topic will be covered in (roughly) one lecture. Lecture notes are linked as they become available.

0. Course introduction

CAs’ homework series intro (on courseworks/Files)
Go tutorial (on courseworks/Files)

1. Distributed systems primer

challenges and goals of distributed systems
example architectures

2. Distributed computation

MapReduce
Spark
Tradeoffs

3. Communication models

remote procedure calls (RPC)
RPC libraries
failure models
semantics

4. Time and coordination

challenges
physical and logical clocks
distributed mutual exclusion

5. Agreement in distributed systems

the atomic commitment problem
the consensus problem
use cases for each
FLP impossibility result of achieving consensus

6. The transaction abstraction

ACID semantics
concurrency control mechanisms
recovery mechanisms

7. Atomic commitment protocols

2-phase-commit
blocking nature

8. Consensus protocols

Paxos overview, key ideas, basic algorithm
examples of normal operation and operation under failures
liveness failure mode
multi-Paxos
applications

9. Case studies from industry

Google’s Spanner scalable, fault-tolerant ACID database
Google’s Chubby fault-tolerant lock service
Google’s Bigtable scalable, fault-tolerant, multi-dimensional, sorted map

10. Broader view of isolation and consistency semantics

isolation: serializability, repeatable reads, read committed, read uncommitted
consistency: external, sequential, causal, eventual
mechanisms for each
performance/usability tradeoffs

11. Beyond storage and MapReduce: Broader infrastructure systems

Google’s software stack
Meta’s software stack
Hadoop and Spark software stacks

12. Cluster scheduling

scheduler architectures and considerations
frameworks: YARN, Mesos, Borg
algorithms: dominant resource fairness, bin packing

13. Testing and model checking

testing approaches and challenges
formal specification and model checking
TLA+ primer