For more up-to-date notes see http://www.cs.yale.edu/homes/aspnes/classes/465/notes.pdf.
Things we can do with a snapshot:
- add up a contribution from each process (gives a counter)
find maximum value (gives a MaxRegister)
The Jayanti, Tan, Toueg lower bound for perturbable objects says each of these objects requires n-1 space and n-1 steps for a read operation in the worst case, for any solo-terminating implementation from historyless objects.
Here perturbable means that the object has a particular property that makes the proof work, essentially that the outcome of certain special executions can be changed by stuffing lots of extra update operations in the middle (see below for details). Solo-terminating means that a process finishes its current operation in a finite number of steps if no other process takes steps in between; it is a much weaker condition, for example, than wait-freedom. Historyless objects are those for which any operation that changes the state overwrites all previous operations (i.e., those for which covering arguments work); atomic registers are the typical example, while swap objects (with a swap operation that writes a new state while returning the old state) are the canonical example since they can implement any other historyless object (and have consensus number 2, showing that even extra consensus power doesn't necessarily help here).
Sketch of proof:
Build executions of the form ΛkΣkΠ, where Λk is a preamble consisting of various complete update operations and k incomplete update operations, Σk delivers k delayed writes from the incomplete operations in Λk, and Π is a read operation whose first k reads are from registers written in Σk.
- Induction hypothesis is that such an execution exists for each k ≤ n-1.
Base case is Λ0Σ0 = empty, covering 0 reads by Π.
Now we look for a sequence of operations γ that change what Π returns in ΛkγΣkΠ (object is perturbable if such a sequence always exists).
- For max register, let γ include a bigger write than all the others.
- For counter let γ include at least n increments.
Why n? With fewer increments, we can make Π return the same value by being sneaky about when the partial increments represented in Σk are linearized.
In contrast, historyless objects (including atomic registers) are not perturbable: if Σk includes a write that sets the value of the object, no set of operations inserted before it will change this value. (This is good, because we know that it only takes one 1 atomic register to implement an atomic register.)
Such a γ must write to some register not covered in Σk.
Find a γ' that writes to the first uncovered register that Π looks at (if none exists, the reader is wasting a step), truncate before that write, and prepend the write to Σk.
In more detail: let γ' = αβδ, where β is the first write by γ' to the first register read by Π that is not covered by Σk. Let Λk+1 = Λkα and Σk+1 = βΣk. So now Λk+1Σk+1Π = ΛkαβΣkΠ and in particular Σk+1 covers the first k+1 registers read by Π.
Note: γ' might be much longer than γ (this will be important later, when we want to get around the JTT lower bound).
- Repeat until we've covered n-1 registers ⇒ there are at least n-1 registers and in the worst case a reader reads all of them.