Concurrent and Distributed Systems

Aims

Concurrency is an essential feature of many databases, programming languages, and operating systems. Distributed systems are also concurrent, and introduce the additional challenge of handling partial failures. This course presents an introduction to both the shared-memory concurrency model commonly used among threads on the same machine, and the message-passing model commonly used in distributed systems. It combines a systems-level overview of how concurrent and distributed systems are implemented with an introduction to the programming models and the theory that help us use and reason about the behaviour of these systems.

Lectures

• Introduction to concurrency. Threads, preemption, parallelism, race conditions, critical sections, mutual exclusion, atomicity, compare-and-swap, load-linked/store-conditional.
• Modelling concurrency. State machines, deadlock, dining philosophers problem, livelock.
• Synchronisation primitives. Semaphores, blocking queues, multi-reader single-writer locks, condition variables, monitors, Java’s “synchronized”.
• Liveness. Requirements for deadlock, deadlock prevention and recovery, priority inversion.
• Transactions. Atomicity, Consistency, Isolation, and Durability (ACID). Serializability, lost updates, strict 2-phase locking, isolation levels, snapshot isolation, multi-version concurrency control (MVCC). Crash recovery, write-ahead logging, checkpoints.
• Models of distributed systems. Message-passing, fault tolerance, RPC. Two Generals Problem, Byzantine Generals Problem, fair-loss links. Crash-stop, crash-recovery, and Byzantine faults. Synchronous, partially synchronous, and asynchronous models, failure detectors.
• Time, clocks, and ordering of events. Physical clocks, clock synchronisation and drift, Network Time Protocol (NTP). Causality, happens-before relation, logical clocks, Lamport clocks, vector clocks.
• Broadcast. Reliable broadcast, gossip protocols. FIFO, causal, and total order broadcast.
• Replication. Idempotence, tombstones, read-after-write consistency, quorums, state machine replication, leader-based replication. Replica consistency, two-phase commit, linearizability, ABD algorithm.
• Consensus. Safety and liveness, FLP result, leader election, the Raft consensus algorithm.
• Eventual consistency. CAP theorem, Conflict-free Replicated Data Types (CRDTs), operational transformation.

Objectives

At the end of the course students should:

• understand the need for parallelism, concurrency, and concurrency control;
• be able to correctly use the synchronisation primitives offered by many programming languages and operating systems;
• be aware of the risks of deadlock, livelock, and how to avoid them;
• understand the properties of transactions, how to use them, how they can be implemented, and their performance characteristics;
• appreciate common models of distributed systems, node and network faults, and their implications for system design;
• understand the notions of time and causality in distributed systems;
• be able to compare various approaches to replication and their consistency properties;
• be familiar with a range of distributed algorithms, such as consensus, causal broadcast, and two-phase commit.

Recommended reading

• Silberschatz, A., Galvin, P.G., and Gagne, G. Operating System Concepts (any edition). Wiley, available online
• Goetz, B. (2006). Java Concurrency in Practice. Addison-Wesley.
• Kleppmann, M. (2026). Designing Data-Intensive Applications, 2nd edition. O’Reilly. Available online (free if you log in with your @cam email address)
• van Steen, M. and Tanenbaum, A.S. (2017). Distributed Systems, 3rd edition. Available online
• Cachin, C., Guerraoui, R. and Rodrigues, L. (2011). Introduction to Reliable and Secure Distributed Programming, 2nd edition. Springer, available online (free access from the Cambridge network)