Time-Space Tradeoffs for Implementations of Snapshots

ABSTRACT A snapshot object is an abstraction of the fundamental problem of obtaining a consistent view of the contents of the shared memory in a distributed system while other processes may concurrently update those contents. A snapshot object stores an array of m components and can be accessed by two operations: an UPDATE that changes the value of an individual component and a powerful SCAN that returns the contents of the entire array. This paper proves time-space tradeoffs for fault-tolerant implementations of a snapshot object from registers that support only read and write operations. For anonymous implementations (where all processes are programmed identically), we prove that a SCAN requires \Omega (n/r) time, where n is the number of processes in the system and r is the number of registers used by the implementation. For the general non-anonymous case, we prove that, for any fixed r, the time required to do a SCAN grows without bound as n increases. These tradeoffs hold even in the case where the snapshot object has just two components. This is the first time a lower bound on the tradeoff between time complexity and the number of registers has been proved for any problem in asynchronous shared-memory systems. We introduce a new tool for proving distributed lower bounds: the notion of a shrinkable execution, from which an adversary can remove portions as necessary