Distributed Systems

Building reliable systems from many machines: partial failure, system models and the fallacies of distributed computing; remote procedure calls, messaging and replicated logs, with deadlines, retries with backoff and jitter, and idempotency keys; physical clock synchronization, Lamport, vector and hybrid logical clocks; consistent cuts and Chandy–Lamport snapshots, mutual exclusion, leases, fencing tokens and leader election; two-phase commit, sagas and the transactional outbox; single-leader, chain, multi-leader and quorum replication with anti-entropy; linearizability, causal and eventual consistency, CAP, PACELC and CRDTs; the FLP impossibility result, Paxos and Byzantine fault tolerance; Raft, etcd and ZooKeeper; partitioning, consistent hashing and caching; failure detection, resilience patterns, SLOs and error budgets; and a capstone geo-distributed payments ledger, with MapReduce, stream processing, Kubernetes control loops and data residency.

CMPUT-450 Year 4 3 credits 12 lessons · 7 h 11 min

Offered by HSM University · Computing Science

This is the American version of this course. See the Canadian version.

What you'll learn

Explain why partial failure, unbounded delay and the absence of shared clocks make distributed systems hard, and state the timing and failure assumptions of a system model.
Design remote interfaces that use deadlines, retries with backoff and jitter, idempotency keys and compatible message formats, and choose between RPC, queues and replicated logs.
Reason about physical clock synchronization and its error, and use Lamport, vector and hybrid logical clocks to order events and detect concurrency.
Identify consistent cuts, apply the Chandy–Lamport snapshot algorithm, and use leases, fencing tokens and term numbers for mutual exclusion and leader election.
Explain two-phase commit and its blocking behavior, and choose among consensus-replicated commit, sagas with compensation and the transactional outbox.
Compare single-leader, chain, multi-leader and leaderless replication, choose quorum sizes, and explain read repair, hinted handoff and Merkle-tree anti-entropy.
Define linearizability, sequential, causal and eventual consistency and session guarantees, apply the CAP and PACELC trade-offs, and design simple CRDTs.
State the consensus problem and the FLP impossibility result, and explain how Paxos preserves agreement through ballots, promises and majority quorums.
Trace Raft leader election, log replication and commitment, explain its safety rules, and describe how coordination services such as etcd and ZooKeeper use consensus.
Partition data by range, hash and consistent hashing with virtual nodes, route requests, handle hot keys, and use caches while managing invalidation and stampedes.
Apply failure detection, redundancy across failure domains, checkpointing and resilience patterns, and manage reliability with SLOs, error budgets and blameless postmortems.
Design a geo-distributed service that meets durability, consistency, latency and data-residency requirements, justifying each choice with the mechanisms of the course.

Course content

12 lessons · 7 h 11 min total · final exam

1 What makes distributed systems hard 38 min · quiz
2 Communication: RPC, messaging and failure 36 min · quiz
3 Time, clocks and ordering 36 min · quiz
4 Global state, snapshots and coordination 36 min · quiz
5 Distributed transactions 35 min · quiz
6 Replication 35 min · quiz
7 Consistency models and the CAP theorem 36 min · quiz
8 Consensus I: impossibility and Paxos 36 min · quiz
9 Consensus II: Raft and coordination services 37 min · quiz
10 Partitioning, scaling and caching 34 min · quiz
11 Fault tolerance, failure detection and resilience patterns 35 min · quiz
12 Capstone: designing a geo-distributed service 37 min · quiz
E Final exam 20 questions

Requirements

Recommended background. You can start any course at any time.

Description

Part of the Science stream, typically taken in year 4.