Efficient Bounded Timestamping from Standard Synchronization Primitives
Benyamin Bashari, Ali Jamadi, Philipp Woelfel · 2023
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.