Bounded timestamps [10, 20] allow a temporal ordering of events in executions of concurrent algorithms. They are a fundamental and well studied building block used in many shared memory algorithms. A concurrent timestamp system keeps track of m timestamps, which is usually greater or equal to the number of processes in the system, n. A process may, at any point, obtain a new timestamp, and later determine a total order of all process's most recent timestamps. Known timestamp algorithms do not scale well in the number of processes. Getting a new timestamp takes at least a linear number of steps, and a lower bound by Israeli and Li [20] implies that each timestamp needs to be represented by at least Ω(m) bits.

The standard single-writer snapshot type allows processes to obtain a consistent snapshot of an array of n memory locations, each of which can be updated by one of n processes. In almost all algorithms, a \Scan operation returns a linearizable snapshot of the entire array. Under realistic assumptions, where hardware registers do not have the capacity to store many array entries, this inherently leads to a step complexity of Ω(n).