A tight time lower bound for space-optimal implementations of multi-writer snapshots
Panagiota Fatourou, Faith Ellen Fich, Eric Ruppert · 2003
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 individual 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.