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)
• Software Transactional Memory
• Barriers

Tutorials

• Tutorial 1: presentation, exercises
• Tutorial 2: presentation, exercises
• Tutorial 3: presentation, exercises
• 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: beginning of the semester, Due: November 12, 2010)
2nd Exercise (Out: beginning of the semester, Due: Decemder 23, 2010 )

Presentations by the Students - 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

Paper Reviews

Each student should review one of the papers of the 1st bunch and one of the papers of the 2nd bunch. Undergraduate students that will attend the course will not due any paper review.

Choices for the 1st Paper Review (Out: beginning of the semester, Due: October 22, 2010)

• Y. J. Joung, ``Asynchronous Group Mutual Exclusion", Proceedings of the 17th ACM Annual Symposium on Principles of Distributed Computing, pp. 51-60, 1998.
• V. Bhatt and P. Jayanti, ``Constant RMR solutions to reader writer synchronization", Proceedings of the 29th ACM Annual Symposium on Principles of Distributed Computing, pp. 468-477, 2010.
• H. Attiya and V. Bortnikov, ``Adaptive and efficient mutual exclusion", Proceedings of the 19th ACM symposium on Principles of Distributed Computing, pp. 91–100,  2000.

Choices for the 2nd Paper Review (Out: beginning of the semester, Due: November 26, 2010)

• 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
• Programming Projects