Efficient Bounded Timestamping from Standard Synchronization Primitives
Date
2023
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Bounded timestamps [9, 19 ] 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 𝑚 timestamps, which is usually greater or equal to the number of processes in the system, 𝑛. 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 [ 19 ] implies that each timestamp needs to be represented by at least Ω(𝑚) bits.
We introduce a slightly different semantics for timestamping, where there is no fixed timestamp value associated with an event. A process can execute operation updateTS() to update its latest timestamp, associating it with the (linearization) point of that operation, and is Earlier (𝑝,𝑞) to determine the temporal order of the latest updateTS() operations executed by processes 𝑝 and 𝑞. Since no static timestamp value is returned by update TS(), the lower bound of Israeli and Li does not apply. We present efficient linearizable and wait-free implementations of these methods using a single bounded
fetch-and-add object and 𝑂 (𝑛²) bounded compare-and-swap objects, which are available on standard hardware. The step complexity of each method call is constant, and base objects need only store 𝑂 (log 𝑛) bits.
Description
Keywords
Theory of computation, Shared memory algorithms
Citation
Bashari, B., Jamadi, A., & Woelfel, P. (2023). Efficient Bounded Timestamping from Standard Synchronization Primitives [Report]. University of Calgary, Calgary, AB.