1. Synchronized leader election
Do Exercise 11.6 from AttiyaWelch.
2. A generalized counter
Consider the following implementation of a generalized counter (supporting arbitrary increments) from a fetch-and-increment register and a large array of registers. The sequential behavior of the generalized counter is that each read operation returns the sum of all previous increments.
(Recall that a fetch-and-increment register supports a single operation fetch-and-increment, which increments the register and returns its old value as a single atomic operation.)
- Shared data
- Fetch-and-increment register c initialized to 0, array a[0..∞] of registers also initialized to 0.
- Increment(delta)
- index ← fetch-and-increment(c)
- a[index] ← delta
- Read()
- index ← fetch-and-increment(c)
- sum ← 0
- for i ← 0 to index do:
- sum ← sum + a[i]
- return sum
Prove or disprove: The generalized counter as implemented above is linearizable.
3. A dead battery object
A battery object is a counter that supports, in addition to the usual operations increment, decrement, and read, two new operations fail and replace. The effect of the fail operation is to set the value of the counter to zero; it remains at zero despite subsequent increment and decrement operations until the next replace operation. After a replace operation, the counter is still at zero, but increment and decrement operations now work. (Any additional replace operations before the next fail operation have no effect; similarly, applying fail to a battery that is already dead has no effect.)
Give a deterministic wait-free linearizable implementation of a battery object from multi-writer multi-reader atomic registers, or show that no such implementation is possible. If you give an implementation, compute the worst-case cost of any battery operation as a function of the number of processes n.