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

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:

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:


2014-06-17 11:58