Abstract:

The snapshot object is an important and well-studied
primitive in distributed computing that allows processes to obtain
a consistent view of an entire block of shared memory, even if updates
to it are being performed concurrently. Specifically, it consists
of an array of components that supports two operations:
UPDATE, which changes the value of some component, and
SCAN, which returns the contents of the entire array.

This talk will present a time-space tradeoff for
fault-tolerant implementations of a snapshot object
in an asynchronous shared memory system in which
processes communicate by reading and writing shared registers.
Specifically, a lower bound will be given for the worst-case number
of steps for a process to perform a SCAN  as a function of
the number of processes and shared registers in the system.

No previous knowledge of distributed computing will be required
to understand the talk.

This is joint work with Panagiota Fatourou and Eric Ruppert,
to appear at STOC 2006.