Evaluation:
Assignments, 35%
Mid-semeseter exam, 25%
Final exam, 40%
Copying is fatal.
Textbook:
The Art of Multiprocessor Programming,On-the-Fly Garbage Collection: An Exercise in
Cooperation
(PDF),
Edsger W. Dikjstra, Leslie Lamport, A.J. Martin,
C.S. Scholten and E.F.M. Steffens,
Communications of the ACM, Vol 21, No 11 (1978) 966–975.
Impossibility of distributed consensus with one faulty process
(PDF),
Michael J. Fischer, Nancy A. Lynch and Michael S. Paterson,
Journal of the ACM, Vol 32, No 2 (1985) 374–382.
Lecture 1, 1 August 2016
Introduction
Lecture 2, 4 August 2016
Mutual exclusion: critical sections, Peterson's algorithm, filter Lock, Lamport's Bakery algorithm. (Herlihy and Shavit, 2.1-2.6)
Lecture 3, 11 August 2016
Mutual exclusion: Filter lock, Lamport's Bakery algorithm, fairness, bounded time stamps, lower bounds on number of variables. (Herlihy and Shavit, 2.5-2.8)
Lecture 4, 22 August 2016
Concurrent objects and correctness: Quiescent consistency, sequential consistency, linearizability. (Herlihy and Shavit, 3.1-3.5)
Lecture 5, 26 August 2016
Concurrent objects and correctness: Formalizing linearizability, progress conditions. (Herlihy and Shavit, 3.6-3.7)
Lecture 6, 29 August 2016
Shared registers: from SRSW safe registers to MRMW multivalue registers, atomic snapshots. (Herlihy and Shavit, 4.1-4.3)
Lecture 7, 1 September 2016
Consensus protocols: consensus numbers for atomic registers and FIFO queues. (Herlihy and Shavit, 5.1-5.4)
Lecture 8, 8 September 2016
Consensus protocols: (m,n)-assignment objects, read-modify-write (RMW) instructions, Common2 RMW operations, compare and set. (Herlihy and Shavit, 5.5-5.8)
Lecture 9, 12 September 2016
Universality of consensus: lock-free universal construction, extending the lock-free construction to a wait-free construction. (Herlihy and Shavit, 6.1-6.3, 6.4 (part))
Lecture 10, 15 September 2016
Universality of consensus: Wait-free construction, with proofs. Supplementary remarks on minimal and maximal progress, blocking vs non-blocking etc (from the slides). (Herlihy and Shavit, 6.4, supplementary slides))
Lecture 11, 29 September 2016
Spin locks and contention: practical considerations, test and set locks (TAS, TTAS), Exponential Backoff, Queue Locks (ALock) (Herlihy and Shavit, 7.1-7.6 (part))
Lecture 11, 29 September 2016
Spin locks and contention: practical considerations, test and set locks (TAS, TTAS), Exponential Backoff, Queue Locks (ALock) (Herlihy and Shavit, 7.1-7.6 (part))
Lecture 12, 3 October 2016
Queue Locks (CLH Lock, MCS Lock), TimeOut Lock, Composite Lock (Herlihy and Shavit, 7.6-7.7)
Lecture 13, 6 October 2016
Quick review of monitors and conditions. (Herlihy and Shavit, 8.1-8.2)
Linked lists: List-based sets, concurrent reasoning (representation invariants, abstraction maps), coarse-grained synchronization, fine-grained synchronization, optimistic synchronization (Herlihy and Shavit, 9.1-9.6)
Lecture 14, 13 October 2016
Linked lists: Lazy synchronization, non-blocking synchronization. (Herlihy and Shavit, 9.7-9.8)
Lecture 15, 17 October 2016
Concurrent queues: Bounded partial queue, unbounded total queue, unbounded lock-free queue, ABA problem. (Herlihy and Shavit, 10.1-10.6)
Concurrent stacks: Unbounded lock-free stack. (Herlihy and Shavit, 11.1-11.2)
Lecture 16, 18 October 2016
Concurrent stacks: Elimination backoff stack. (Herlihy and Shavit, 11.3-11.5)
Locks and conditions: Lost wakeup, and concurrent queues. (Herlihy and Shavit, 8.2, 10.2)
Concurrent garbage collection: introduction. (Paper by Dijkstra et al)
Lecture 17, 20 October 2016
Concurrent garbage collection: the model, mark and sweep, sequential vs concurrent GC, coarse grained solution (Paper by Dijkstra et al)
Lecture 18, 24 October 2016
Concurrent garbage collection: Fine grained solution (Paper by Dijkstra et al)
Lecture 19, 27 October 2016
Impossibility of distributed consensus with one faulty process (Paper by Fischer, Lynch and Paterson)
Lecture 20, 10 November 2016
Distributed counting: combining tree. (Herlihy and Shavit, 12.1-12.3)
Lecture 21, 14 November 2016
Distributed counting: Bitonic counting network, sorting networks (Herlihy and Shavit, 12.5 (part), 12.8 (part))