Introduction to Distributed Systems

Keeping a service correct when messages are lost and machines fail

About this course

Building services across machines that fail independently — remote calls and retries, causality and logical time, replication and consistency, consensus and Raft, distributed transactions, partitions, sharding and testing.

What you will be able to do

  • Explain what a client can conclude when a reply never arrives, and design idempotent retries
  • Order events with logical clocks and identify causal relationships
  • Compare primary-backup and quorum replication by the consistency each provides
  • Trace Raft leader election and log replication through failures
  • Analyse a distributed transaction or partition scenario and state which guarantees still hold

What this course covers

  • Replication and the consistency contract problem
  • Linearizability: definition and point-placement test
  • Sequential specification of the register object
  • Operation intervals as the unit of history
  • Stale read as a linearizability violation
  • Cycle-based rejection: the two-read counterexample
  • Sequential consistency vs. linearizability
  • Eventual convergence does not imply linearizability
  • Motivation: why independent local calls fail
  • Two-phase commit: messages, records, and state transitions
  • Prepared state: obligation, not completion
  • Unanimity requirement vs. replication quorums
  • Coordinator's durable decision boundary
  • Blocking under coordinator failure and the two-worlds argument
  • Atomic outcome vs. visibility, isolation, and compensation
  • Closing synthesis: retained evidence and protocol boundaries
  • Timeout ambiguity and partial failure
  • Four objects: intention, message, effect, reply
  • Sequence-diagram model of remote execution
  • Retry and the duplicate-effect defect
  • Operation identity and duplicate recognition
  • Atomicity gap between effect and recognition record
  • Safety vs. liveness: duplicate bound vs. eventual result
  • Correct duplicate-recognition trace and design foundations
  • Crash gap between effect and progress recording
  • Distinguishing deliveries, processing attempts, and accepted effects
  • Atomic destination transaction coupling effect and progress
  • Log record identity versus business event identity
  • Outbox pattern and limits of local intent durability
  • Generation fencing for stale workers
  • Event time versus arrival time and late-event handling
  • Backlog growth and processing capacity limits
  • Separating retained evidence types and closing summary
  • Why majority intersection alone is insufficient
  • Consensus problem definition and specification
  • One-vote toy rule and its safety argument
  • Progress failure of the one-vote rule (split-vote stall)
  • Why free vote changes destroy safety
  • Asynchronous model and limits of timeout-based inference
  • FLP impossibility boundary and practical progress assumptions
  • Explicit scheduling for reproducible failure investigation
  • Atomic duplicate suppression model and safety predicate
  • Test harness structure and negative controls
  • Linearizability checking for a single register
  • Handling operations with unknown outcomes
  • Trace shrinking to minimal counterexample
  • Bounded search scope, checker outcomes, and test limits
  • Scope and goals of the election lesson
  • Crash recovery and vote persistence
  • Node state fields and term-driven role transitions
  • Majority overlap and the single-vote-per-term rule
  • Duplicate responses and campaign-context vote counting
  • Split elections, term advancement, and progress
  • Stale and higher-term message handling
  • Log freshness voting restriction
  • Lecture summary: safety, progress, and what election alone cannot establish
  • Preserving accepted state vs. controlling authority
  • Replicated application state: what a backup must retain
  • Acknowledgement rule: holding responses behind backup retention
  • Three crash-cut analysis with retry
  • Authority separation: partition vs. crash
  • Generation-based fencing at a protected resource
  • Atomicity of generation check and effect (check-then-act race)
  • Snapshot and ordered suffix for replacement backup
  • Scope, assumptions, and limits of the constructions
  • Atomic ownership claim for concurrent handlers
  • Operation identity vs. payload equality
  • Three-state request record: absent, pending, completed
  • Atomic durable transaction as the effect boundary
  • Effects outside the transaction boundary
  • Identity evidence retention and expiration
  • Scoped guarantee, safety vs. progress, and retry scheduling
  • Network partition and the coordination problem
  • Linearizability and operation-interval histories
  • Safety vs. progress under partition
  • The information-gap argument against local guessing
  • Weaker contracts: local reads, explicit errors, and API clarity
  • Recovery, convergence, and the immutability of past observations
  • Pre-allocated writes as bounded local authority
  • Bounded checker scope and the complete operation contract
  • Happened-Before Relation and Event Graphs
  • Concurrency as Absence of Directed Reachability
  • Scalar Logical Clocks (Lamport Timestamps)
  • One-Way Property and Limits of Scalar Clocks
  • Vector Clocks: Construction and Update Rule
  • Vector Clock Comparison and Causal-Concurrency Detection
  • Total Order via Deterministic Tiebreak
  • Matching the Instrument to the Claim
  • Three separate progress boundaries: stored, committed, applied
  • Replicated log structure and entry fields
  • Prefix check and suffix repair for log extension
  • Idempotent log append and ordered application
  • Confirmed matching positions and the current-term commitment rule
  • Why the current-term rule prevents premature commitment: the two-branch contrast
  • Follower commitment propagation and the apply loop in practice
  • Two-level sharding architecture and shard movement motivation
  • Why complete state transfer is required
  • Placement functions and key movement under map changes
  • Durable freeze, epoch-checked writes, and the at-most-one-owner rule
  • Transfer bundle contents and installation vs. activation as separate states
  • Idempotent transfer messages and freeze-ordering with concurrent writes
  • Joint-configuration quorum for replica membership changes
  • End-to-end correctness summary and recovery obligations
  • Reservation service state machine and atomicity
  • Inventory conservation invariant
  • Stable historical response semantics
  • Authority contract: failover, obsolete leaders, and minority partitions
  • Outbox pattern and receiver idempotency contract
  • Precise end-to-end correctness claims vs. 'exactly-once' label
  • Bounded testing, negative controls, and identity retention limits
  • End-to-end design checklist and course synthesis
  • Quorum overlap: the intersection counting argument
  • Acknowledgement thresholds, durability, and availability trade-offs
  • Completed-write lower bound on observed tag
  • Partial-write counterexample to naive majority reads
  • Read propagation as a repair mechanism
  • Concurrent version vectors and causal incomparability
  • Membership counterexample: fallback holders break the intersection proof

Syllabus

  1. Failures, Remote Calls and Time

    1. L1 · When a Reply Never Arrives
    2. L2 · Remote Calls and Retry Semantics
    3. L3 · Time, Events, and Causality

  2. Replication and Consistency

    1. L4 · Replication and Consistency
    2. L5 · Primary-Backup Replication
    3. L6 · Quorums and Versioned Data

  3. Consensus and Raft

    1. L7 · Consensus and Its Limits
    2. L8 · Raft: Electing a Leader
    3. L9 · Raft: Replicating a Log

  4. Transactions, Partitions and Sharding

    1. L10 · Transactions Across Machines
    2. L11 · Partitions and Availability
    3. L12 · Sharding and Reconfiguration

  5. Streams, Testing and Synthesis

    1. L13 · Streams and Repeated Delivery
    2. L14 · Testing Distributed Executions
    3. L15 · One Service Through Failures