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: October 18, 2012, Due: November 5, 2012)
2nd Exercise (Out: October 18, 2012, Due: December 14, 2012)

Student Presentations - Possible Topics

Schedule of presentations

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

Paper Reviews

Each student should review one of the following papers. Undergraduate students that will attend the course will not due any paper review.

Choices for the Paper Review (Out: beginning of the semester, Due: December 05, 2011)

• P. Jayanti, ``f-arrays: implementation and applications", Proceedings of the 21st ACM Symposium on Principles of Distributed Computing, pp. 270 – 279, 2002.
• G. Barnes, ``A method for implementing lock-free shared-data structures", Proceedings of the 5th ACM symposium on Parallel algorithms and architectures , pp. 261–270, 1993.
• Y. Afek, D. Dauber, and D. Touitou, ``Wait-free made fast", Proceedings of the  ACM Symposium on Parallel Algorithms and Architectures, pp. 538–547, 1995.

How to Review a Paper in Theoretical Computer Science

• Ian Parbery,A Guide for new Referees in Theoretical Computer Science
• A manual for authors of mathematical papers by American Mathematical Society
• Indicative Review Form for Research Papers in Theoretical Computer Science

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 18, 2012)
• Programming Projects (Out: October 18, 2012)
(Proposal due: December 03, 2012, Due: January 21, 2013)

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.