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 Λ₀Σ₀ = 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.

CategoryDistributedComputingNotes