1. Synchronized leader election

Do Exercise 11.6 from AttiyaWelch.

1.1. Solution

Again we will we give only a hint at a solution to prevent future classes from using this problem. The short answer is that the message complexity of both leader election algorithms is very bad: the alpha synchronizer sends a message between each adjacent pair of nodes in every round, even if the underlying algorithm is silent.

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.

2.1. Solution

It's not linearizable; the fetch-and-increments are a distraction from the use of standard collects in Read(). Consider processes 0, 1, 2, and 3, where 0 and 1 execute Increment with deltas 1 and 2, respectively, and 2 and 3 execute Read. Suppose that each process i obtains the value i from the fetch-and-increment object. Now order the subsequent operations as follows:

1. 2 reads 0 from a[0]
2. 0 writes 1 to a[0]
3. 3 reads 1 from a[0]
4. 3 reads 0 from a[1]
5. 1 writes 2 to a[1]
6. 2 reads 2 from a[1]
7. 2 and 3 complete their Read operations.

Then 2's Read returns 2 while 3's returns 1. There is no way to order the two Increments in a sequential execution so that both these values are present in the counter during the execution. It follows that the implementation is not 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.

3.1. Solution

Looking at the operations, we see that all of them either commute (increments) or overwrite (fail and replace). So we expect to be able to implement this from atomic registers. A natural approach is to use snapshots.

We'll use an array a indexed by process identities, where each segment of the array consists of separate fields for recording fail/replace operations and recording increments. Each of these fields is further subdivided into a timestamp and a summary (fail or replace for the fail field and a total increment for the counter field). The interpretation is that the fail/replace field gives the time of the last fail or replace operation carried out by this process, while the increment field gives the total increment performed since the replace operation with the given timestamp.

Here are the operation implementations. For simplicity, we combine fail/replace and increment/decrement into single parameterized operations.

fail/replace(op)

• s ← snapshot(a)

• ts ← max_i s[i].fail.timestamp

• a[i].fail.op ← (ts+1, op)

increment(delta)

• s ← snapshot(a)

• ts ← max_i s[i].fail.timestamp

• if there is some j with s[j].fail.timestamp = ts and s[j].fail.op = fail:

  • do nothing
• else:
  • if a[i].increment.timestamp = ts:
    • a[i].increment.total ← a[i].increment.total + delta
  • else:
    • a[i].increment ← (ts, delta)

read

• s ← snapshot(a)

• ts ← max_i s[i].fail.timestamp

• if there is some j with s[j].fail.timestamp = ts and s[j].fail.op = fail:

  • return 0
• else:
  • return ∑ s[j].counter.total for all j such that s[j].counter.timestamp = ts

We now need to prove that this is linearizable. Given an execution of the protocol, define the round of each operation as the value of ts it computes (for increment and read operations) or ts+1 (for fail/replace operations). Observe that since timestamps only increase, and each operation that has a higher round number than it reads writes its new round number, it is the case that if op1 precedes op2, then round(op1) ≤ round(op2), with strict inequality for fail/replace operations. So we can sort operations by round without violating linearization.

We still need to sort operations within each round. Our policy is (all replace operations) < (any read and increment operation that doesn't observe a failure) < (all fail operations) < (any read or increment operation that observes a failure). Note that since the replace and fail operations all have the same timestamp, none of them observes the values written by any of the others, and thus they are all concurrent. So we can order them freely. For read and increment operations, the monotonicity of the snapshots implies that any read or increment that doesn't observe a failure does its snapshot before any fail operation's write, and any that does does its snapshot after the write, so again this partial ordering is consistent with the underlying execution. Finally, within the two classes of reads and increments, we order operations based on when they do their critical step: snapshots for reads, and writes for increments. This gives a total order of all high-level operations.

We now argue that the return value of the reads are consistent with this ordering; this proves it is a linearization since no other operations return anything. If a read operation sees a failure in its round, it is ordered after some failure but before any subsequent replacements. Its return value of 0 is consistent with the dead battery it would have observed in the sequential execution. If it doesn't see a failure, it returns the sum of all total increments it sees in this round; this includes precisely those increment operations that are also ordered before the first failure that perform their writes before the read's snapshot. But these are the increment operations ordered before it in the sequential ordering, so again the return value is correct.