Abstract:

A snapshot object consists of a collection of $m > 1$ components, each
capable of storing a value, shared by $n$ processes in an asynchronous
shared-memory distributed system. It supports two operations: a process
can UPDATE any one component or atomically SCAN the entire collection to
obtain the values of all the components. It is possible to implement a
snapshot object using $m$ registers so that each operation takes $O(mn)$
time.

We prove that $m$ registers are necessary to implement a snapshot object
with $m < n$ components. We also prove that, for any such space-optimal
implementation, $\Omega(mn)$ steps are required to perform a SCAN
operation in the worst case. Our proof yields insight into the structure
of any space-optimal implementation, showing that processes must access
the registers in a very constrained way.

This work is joint with Panagiota Fatourou (University of Ioannina,
Greece) and Eric Ruppert (York University).