[FrontPage] [TitleIndex] [WordIndex

Note: You are looking at a static copy of the former PineWiki site, used for class notes by James Aspnes from 2003 to 2012. Many mathematical formulas are broken, and there are likely to be other bugs as well. These will most likely not be fixed. You may be able to find more up-to-date versions of some of these notes at http://www.cs.yale.edu/homes/aspnes/#classes.


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.
  • index ← fetch-and-increment(c)
  • a[index] ← delta
  • 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.

2014-06-17 11:58