Computer Laboratory

Course pages 2011–12

Concurrent and Distributed Systems

There are four handouts available for the first part of the course (Concurrent Systems):

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.

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.

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