We consider the problem of wait-free implementation of a multi-writer snapshot object with m ≥ 2 components shared by n > m processes. It is known that this can be done using m multi-writer registers. We give a matching lower bound, slightly improving the previous space lower bound. The main focus of the paper, however, is on time complexity. The best known upper bound on the number of steps a process has to take to perform one operation of the snapshot is O(n). When m is much smaller than n, an implementation whose time complexity is a function of m rather than n would be better. We show that this cannot be achieved for any space-optimal implementation: We prove that Ω(n) steps are required to perform a SCAN operation in the worst case, even if m = 2. This significantly improves previous Ω(min(m, n)) lower bounds. Our proof also yields insight into the structure of any space-optimal implementation, showing that processes simulating the snapshot operations must access the registers in a very constrained way.
展开▼
