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