Madhavan Mukund



Concurrent Programming

Aug–Nov, 2016


Administrative details

  • Evaluation:

    • Assignments, 35%

    • Mid-semeseter exam, 25%

    • Final exam, 40%

    • Copying is fatal.

  • Textbook:

    The Art of Multiprocessor Programming,
    Maurice Herlihy and Nir Shavit,
    Mogan Kaufman (2008)

Reading material

  • 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.


Course plan

  • Mutual Exclusion
  • Concurrent objects, notions of correctness
  • Shared registers
  • Consensus protocols
  • Universality of consensus
  • Locks
  • Concurrent lists and queues
  • Some topics in distributed algorithms (to be finalized)


Lecture summaries

  • 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))

p