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. Consensus numbers of tagged registers

A tagged register is a register that supports read and write operations on pairs (tag, value) where each tag is an element of some totally-ordered set and each value is arbitrary. The purpose of the tags is to prevent lost updates: a write with an tag smaller than the current value in the register will be discarded. Read operations return the current value of the register as usual.

Consider the following variants of tag registers, which differ in how they handle writes with tags equal to the current tag. For each variant, determine its consensus number (as defined in WaitFreeHierarchy).

Writes with tags equal to the current tag go through as usual.
Writes with tags equal to the current tag are discarded.
Writes with tags equal to the current tag cause the register to go into a special failure state. Any subsequent read returns failure and any subsequent write has no effect.

2. Counters

Here is an implementation of a counter from atomic registers. Each process maintains a register whose value is equal to the number of increment operations carried out by that process; to execute an increment operation, the process increases the value in its register by 1. To read the counter, a process reads all the registers one at a time and sums up their values.

Is this counter linearizable?¹
Suppose we use the same mechanism to build a generalized counter, where an increment operation may increase or decrease the value of the counter by an arbitrary amount, not just +1. Is the resulting object linearizable?

Recall that an implementation is linearizable if, for every execution, there is a sequential execution of the simulated object such that if operation A finishes before operation B starts in the actual execution, operation A comes before operation B in the sequential execution. Equivalently, an implementation is linearizable if we can assign some time within the interval spanned by each operation such that we get a sequential execution of the simulated object if we treat each operation as happening atomically at its assigned time. (1)