Space-Efficient Atomic Snapshots in Synchronous Systems

We consider the problem of implementing an atomic snapshot memory in synchronous distributed systems. An atomic snapshot memory is an array of memory locations, one per processor. Each processor may update its own location or scan all locations atomically. We are interested in implementations that are space-efficient in the sense that they are honest. This means that the implementation may use no more shared memory than that of the array being implemented and that the memory truly reflect the contents of that array. If n is the number of processors involved, then the worst-case scanning time must be at least n. We show that the sum of the worst-case update and scanning times must be greater than floor(3n/2). We exhibit two honest implementations. One has scans and updates with worst-case times of n+1 for both operations; for scans, this is near the lower bound. The other requires longer scans (with worst-case time ceiling(3n/2)+1) but shorter updates (with worst-case time ceiling(n/2)+1). Thus, both implementations have the sum of the worst-case times at 2n + O(1), which is within n/2 of the lower bound. Closing the gap between these algorithms and the combined lower bound remains an open problem