Course Slides and other Material

Course Slides

• Introduction- Synchronization - Modeling (Section 1)
• Mutual Exclusion (Section 2)
• PRACTICE: Spin Locks and Contention (Section 3)
• Concurrent Objects - Correctness, Progress and Efficiency Snapshot Objects(Section 4)
• Foundation of Shared Memory: Fault-Tolerant Simulations of read/write objects(Section 5)
• Fault-Tolerant Consensus(Section 6)
• Wait-Free Simulations of Arbitrary Objects(Section 7)
• Concurrent Pools (Queues, Stacks, Lists)(Sectrion 8)
• Safe Memory Reclamation(Section 9)
• Barriers(Section 10)
• Software Transactional Memory

Tutorials

• Tutorial 1: presentation
• Tutorial 2: presentation
• Tutorial 3: presentation
• Tutorial 4: presentation
• Tutorial 5: presentation, Technical Report of "Time-Oprimal, Space-Efficient Single-Scanner Snapshots & Efficient Multi-Scanner Snapshots using CAS"

Assignments

1st Exercise (Out: November 18, 2013, Due: November 27, 2013)
2nd Exercise (Out: November 01, 2013, Due: December 23, 2013)

Student Presentations - Possible Topics

Each student should choose to present one of the following topics:

• Fast Mutual Exclusion Algorithms: Section 2.2, book G. Taubenfeld, Synchronization Algorithms and Concurrent Programming, Pearson Prentice Hall, 2006.
• Local Spinning Mutual-Exclusion Algorithms: Section 3.1, book G. Taubenfeld, Synchronization Algorithms and Concurrent Programming, Pearson Prentice Hall, 2006.
• Adaptive Mutual-Exclusion Algorithms: Section 3.2, book G. Taubenfeld, Synchronization Algorithms and Concurrent Programming, Pearson Prentice Hall, 2006.
• The Ticket Algorithm using RMW Objects: Section 4.3, book H. Attiya and J. Welch, Distributed Computing, Fundamentals, Simulations and Advanced Topics, Mc Graw Hill, 1998.
• The l-Exclusion Problem, Algorithms using atomic registers: Section 6.2, book G. Taubenfeld, Synchronization Algorithms and Concurrent Programming, Pearson Prentice Hall, 2006.
• The l-Exclusion Problem, Usign a single RMW register: Section 6.3, book G. Taubenfeld, Synchronization Algorithms and Concurrent Programming, Pearson Prentice Hall, 2006.
• Multiple Resources, Deadlock Prevention: Sections 7.1, 7.2, book G. Taubenfeld, Synchronization Algorithms and Concurrent Programming, Pearson Prentice Hall, 2006.
• Multiple Resources, Deadlock Avoidance: Sections 7.1, 7.3, book G. Taubenfeld, Synchronization Algorithms and Concurrent Programming, Pearson Prentice Hall, 2006.
• Multiple Resources, The Dinning Philosophers Problem: Sections 7.1, 7.4, book G. Taubenfeld, Synchronization Algorithms and Concurrent Programming, Pearson Prentice Hall, 2006.
• Multiple Resources, Hold and Wait Strategy & Wait and Release Strategy: Sections 7.1, 7.5, 7.6, book G. Taubenfeld, Synchronization Algorithms and Concurrent Programming, Pearson Prentice Hall, 2006.
• Classical Synchronization Problems, The Producer-Consumer Problem: Sections 8.1, book G. Taubenfeld, Synchronization Algorithms and Concurrent Programming, Pearson Prentice Hall, 2006.
• Classical Synchronization Problems, Readers and Writers: Section 8.2, book G. Taubenfeld, Synchronization Algorithms and Concurrent Programming, Pearson Prentice Hall, 2006.
• Classical Synchronization Problems,  The Sleeping Barber and the Cigarette Smoker's Problems: Section 8.3, 8.4, book G. Taubenfeld, Synchronization Algorithms and Concurrent Programming, Pearson Prentice Hall, 2006.
• More Synchronization Problems: Section 8.5, book G. Taubenfeld, Synchronization Algorithms and Concurrent Programming, Pearson Prentice Hall, 2006

Project

Students can choose whether they prefer to work on a theory or on a programming project. In case a student chooses to work on a theory project, s/he may choose a research topic relevant to the course material as his/her project's topic. Suggestions by the instructor will also be provided soon.
• Theory Projects (Out: October 07, 2013)
• Programming Projects (Out: October 07, 2013)
(Proposal due: December 01, 2013, Due: January 27, 2014)

Final Exam

Here is the material that you should study for the final exam:

• M. Herlihy and N. Shavit, "The art of multiprocessor programming", Morgan Kauffman, 2008

  - Sections 1.1, 1.5, 7.1 to 7.5, 7.9, and 7.10, Chapters 9, 10, 11, 17

• H. Attiya and J. Welch, "Distributed Computing: Fundamentals, Simulations, and Advanced Topics", John Wiley and Sons, 2004

  - Chapter 1, Sections 4.1, 4.2, 4.3, 4.3.1, 4.3.2, (don't read 4.3.3), 4.4.2, 4.4.3, Chapters 10 (only Sections 10.1 and 10.2), 15

• G. Taubenfeld, "Synchronization Algorithms and Concurrent Programming", Pearson / Prentice Hall, 2006

  - Sections 2.1, 2.1.1, (don't read 2.1.2), 2.3, 2.4, 2.5.2,

• N.Lynch, "Distributed Algorithms", Morgan Kauffman, 1996

  - Sections 10.8, 13.3 (only 13.3.1 and 13.3.2), Chapter 12 (only 12.1 to 12.2.4)

Research Papers:

• Maurice P. Herlihy and Jeannette M. Wing. 1990. Linearizability: a correctness condition for concurrent objects. ACM Trans. Program. Lang. Syst. 12, 3 (July 1990), 463-492.

  - Sections 1 to 3

• Maged M. Michael. 2004. Hazard Pointers: Safe Memory Reclamation for Lock-Free Objects. IEEE Trans. Parallel Distrib. Syst. 15, 6 (June 2004), 491-504.

  - Sections 4.1 to 4.3

Optional:

• M. Herlihy and N. Shavit, "The art of multiprocessor programming", Morgan Kauffman, 2008

  - Chapter 3, 16, and B

• Research Paper: Nimar S. Arora, Robert D. Blumofe, and C. Greg Plaxton. 1998. Thread scheduling for multiprogrammed multiprocessors. In Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures (SPAA '98). ACM, New York, NY, USA, 119-129.