CS 85/185 (Concurrent Algorithms) Journal

1. Lecture 01, Thursday, September 23, 2010
   • Several formulations of the Forehead problem (Muddy children puzzle)
   • A discussion of levels of knowledge and common knowledge

2. Lecture 02, Tuesday, September 28, 2010
   • Specifications of Coordinated Attack and Weak Coordinated Attack Problems
   • Unsolvability of (the strong version of) Coordinated Attack Problem
   • Relation to the Commit Problem in databases

3. Lecture 03, Thursday, September 30, 2010
   • Unsolvability of Weak Coordinated Attack Problem
   • Started Mutual Exclusion
   • Homework 1 given out, due October 7

4. Lecture 04, Tuesday, October 5, 2010
   • Peterson's 2-process Mutual Exclusion algorithm
   • Specification of Mutual Exclusion problem
   • Peterson's n-process Mutual Exclusion algorithm
   • First-Come-First-Served (FCFS) property and Lamport's Bakery algorithm

5. Lecture 05, Thursday, October 7, 2010
   • Discussion and statement of First-Come-First-Served (FCFS) property
   • Started Lamport's Bakery algorithm
   • Homework 2 given out, due October 14

6. Lecture 06, Tuesday, October 12, 2010
   • Bakery algorithm
   • Cache-Coherent (CC) and Distributed Shared Memory (DSM) models, RMR complexity

7. Lecture 07, Thursday, October 14, 2010
   • Anderson's constant RMR algorithm for the CC model
   • MCS constant RMR algorithm for the DSM (and CC) models
   • Homework 3 given out, due October 21

8. Lecture 08, Tuesday, October 19, 2010
   • Other exclusion problems: l-exclusion, readers/writers
   • Discussion of First-In-First-Enabled and Concurrent Entering properties

9. Lecture 09, Thursday, October 21, 2010
   • Consensus Problem: definition, algorithm using fetch&add
   • Proof of impossibility using read/write objects upto the statement of the two lemmas
   • No homework this week
10. Lecture 10, Tuesday, October 26, 2010
    • Proof concluded, with the proof of the two lemmas.
    • Discussion of related results: wait-free consensus versus t-tolerant consensus; impossibilities using stronger primitives and in message passing. Some results are covered in this week's homework.
    • Homework 4 given out, due November 4
11. Lecture 11, Thursday, October 28, 2010
    • Proof of impossibility of 1-tolerant consensus using registers
12. Lecture 12, Tuesday, November 2, 2010
    • The Implementation Problem
    • Object Type
    • Linearizability
    • Equivalence of linearizability and atomicity
13. Lecture 13, Thursday, November 4, 2010
    • Nonblocking and Wait-free
    • An example of a linearizable implementation: register from CAS
    • Consensus Hierarchy & proofs of impossibility
    • LL/SC operations
14. Lecture 14, Tuesday, November 9, 2010
    • f-Arrays
    • Homework 5 given out, due November 18
15. Lecture 15, Thursday, November 11, 2010
    • Herlihy's universal construction
16. Lecture 16, Tuesday, November 16, 2010
    • Bounding the space in the universal construction
    • Implementing LL/SC from CAS
17. Lecture 17, Thursday, November 18, 2010
    • Constant time, linear space implementation of LL/SC from CAS
    • Assertional proof technique: illustrated by proving Anderson's mutex algorithm
    • Homework 6 given out, due November 30
18. Lecture 18, Tuesday, November 23, 2010
    • Miscellaneous topic: tradeoff between RMR and space complexity
    • Miscellaneous topic: Obstruction-free implementations (example: snapshot)
19. Lecture 19, Tuesday, November 30, 2010
    • Miscellaneous topic: Self-stabilization
    • Miscellaneous topic: Byzantine agreement
    • Miscellaneous topic: Deadlock detection in message passing systems
20. Final Exam
    • Final Exam