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, exercises
• Tutorial 2: presentation, exercises
• 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: beginning of the semester, Due: December 19, 2011)
2nd Exercise (Out: beginning of the semester, Due: January 09, 2012)

Presentations by the Students - Possible Topics

Suggested 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 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: December 26, 2011)
• Programming Projects (Out: beginning of the semester)
(Proposal due: January 10, 2012, Due: February 13, 2012)