Central article:

* Maurice Herlihy, "Wait-Free Synchronization", ACM Transactions on
  Programming Languages and Systems, vol. 13(1), 124-149, 1991.

Questions:

(General)

1. Do wait-free objects guarantee
    -- liveness?
    -- fairness?

2. Do wait-free objects prevent
    -- deadlock?
    -- livelock?
    -- starvation?

3. Explain the difference between "wait-free" and "nonblocking".


(Automata)

4. Why are automata that share internal or ouput events incompatible?

5. Why are compatible automata allowed to share input events?


(Consensus numbers)

6. Give a proof that the consensus number for FIFO queues is n >= 2
   WITHOUT assuming the queue is initialised to a non-empty state.
   (I.e., write a program that obtains 2-process consensus).

(Only do *one* of the following:)

7a. Select one class of concurrent objects: stacks, double-ended
    queues, priority queues or sets.  Define the operations for the
    object class.

7b. Prove Theorem 6 for the object class:  The consensus number for
    the object class is n >= 2.

7c. Prove that the consensus number for the object class is n < 3.
    (cf. the proof of Theorem 7.)