Time-space tradeoffs for implementations of snapshots

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 Ω(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.

Authors

• Panagiota Fatourou
• Faith Ellen
• Eric Ruppert

Keywords

• anonymous processes
• distributed computing
• lower bound
• shared memory
• snapshot
• time-space tradeoff
• wait-free