Course pages 2011–12
Concurrent and Distributed Systems
There are four handouts available for the first part of the course (Concurrent Systems):
- Concurrent Systems Handout 1 [PDF, 1up] [PDF, 4up]
- Concurrent Systems Handout 2 [PDF, 1up] [PDF, 4up]
- Concurrent Systems Handout 3 [PDF, 1up] [PDF, 4up]
- Concurrent Systems Handout 4 [PDF, 1up] [PDF, 4up]
There is also an examples sheet for the first part of the course (thanks to Alastair Beresford!). This may be useful for supervisions, or revision.
- Examples sheet [PDF]
The handouts for the second part of the course (Distributed Systems) will be made available here as the course progresses:
- Distributed Systems Handout 1 [PDF, 1up] [PDF, 4up]
- Distributed Systems Handout 2 [PDF, 1up] [PDF, 4up]
- Distributed Systems Handout 3 [PDF, 1up] [PDF, 4up]
- Distributed Systems Handout 4 [PDF, 1up] [PDF, 4up]
- Erratum: on p26, the signature for the reduce function was originally given as "reduce(key', value')" -- however the reduce function actually takes a list of values for each key (as it combines the output from the various mappers).
There is also some additional material which may be useful; the first three links are to the blog of an SRG alumnus and explaining 2PC, 3PC and Paxos for those interested in more details. The fourth is a set of case studies (distributed storage systems) which may be useful for those interested in learning more about replication, consistency and fault-tolerance.
- Two-Phase Commit (2PC)
- Three-Phase Commit (3PC)
- Paxos (and an implementation)
- Distributed Storage Systems (case studies) [PDF, 1up]
Certain exam questions from previous years (and previous courses) are suitable. The following lists a selection of questions and the assocaited topics they cover (with thanks to Daniel Thomas!).
- y1993p5q7 Atomic operations, transactions, crash recovery
- y1993p6q7 Monitors, N resource allocation, Active objects
- y1994p5q7 Semaphores, MRSW, critical regions
- y1994p6q7 Transactions, ACID, execution schedules, cascading abort, strict vs non-strict, 2PL, TSO
- y1995p3q1 Transactions, ACID, OCC, Isolation enforcement
- y1996p3q1 Transactions, serializability, history graph, isolation enforcement (solution - supervisors only)
- y1997p3q2 MRSW, semaphores, conditional critical regions, monitors, guarded commands
- y1997p4q2 serializability, transactions, Durability
- y1998p4q2 Deadlock, resource allocation graph, deadlock detection algorithm (solution - supervisors only)
- y1998p11q6 semaphores, monitor, barber problem
- y1999p3q1 semaphores, user threads, kernel threads, multi-core (solution - supervisors only)
- y1999p4q2 fail-stop, transactions, RPC
- y1999p10q8 uni/multi-core processes, OS
- y1999p11q6 Sempahores, Producer-consumer, monitors
- y2000p3q1 monitors, semaphores, n resource allocation (same as y2000p10q8)
- y2000p4q1 transactions, S2PL
- y2001p3q1 transactions, ACID, Isolation, 2PL, TSO, OCC
- y2001p4q2 synchronous message passing
- y2002p5q4 Java, barber problem
- y2002p6q4 Transactions, non/strict-isolation, S2PL, OCC, (TSO)
- y2003p5q4 safety, liveness, mutex, deadlock, dining philosophers, Java, starvation
- y2003p11q6 mutex, condition synchronisation, interrupts, R-A-C, sempahores
- y2004p4q8 Java, locking granularity
- y2004p6q4 Transactions, write-ahead log, roll-back, fail-stop, checkpoints (solution - supervisors only)
- y2005p5q4 Java, mutex, synchronized, deadlock, semaphores, C-A-S
- y2005p6q4 Transactions, non/strict isolation, cascading aborts, OCC, deadlock, write-ahead log, checkpoints, recovery algorithm
- y2006p5q4 Java, notify/All, InteruptedException, Deadlock detection algorithm
- y2007p4q1 Transactions, serializable ordering, TSO, history graph, OCC
- y2008p11q9 OS, buffering, mutex, condition synchronisation, interrupts, R-A-C, semaphores, producer consumer, MRSW
- y2009p3q3 Transactions, ACID, serializable execution, non/strict isolation, bad schedules, 2PL, OCC, cascading aborts
- y2009p5q6 Java, synchronized, volatile, notify/All, InterruptedException
- y2010p5q4 MRSW, semaphores, monitors, synchronized, active objects, guarded commands (solution - supervisors only)
- y2010p5q5 Transactions, serializability, conflicting operations, S2PL, STSO, OCC
- y2011p5q7 conflicting operations, TSO, cascading aborts, deadlock, 2PL
- y2011p5q8 part a) semaphores