# 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*.