Treffer: Efficient bounded timestamping from standard synchronization primitives.

Bounded timestamping systems (Israeli and Li in Proceedings of the 28th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp 371–382, 1987; Dolev and Shavit in SIAM J Comput 26 (2):418–455, 1997) 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 (Haldar and Vitányi in J ACM, 49 (1):101–126, 2002; Afek et al. in ACM Trans Program Lang Syst 16:939–953, 1994; Abrahamson in Proceedings of the 7th ACM symposium on principles of distributed computing (PODC), pp 291–302, 1988; Bashari and Woelfel in Proceedings of the 40th ACM symposium on principles of distributed computing (PODC), pp 545–555, 2021). A concurrent bounded timestamping 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 bounded timestamping algorithms (Dolev and Shavit in SIAM J Comput 26(2):418–455, 1997; Dwork and Waarts in J ACM 46(5):633–666, 1999; Dwork et al. in SIAM J Comput 28(5):1848–1874, 1999; Gawlick et al. in Theory of computing and systems (ISTCS), pp 171–183, 1992; Israeli and Pinhasov in Distributed algorithms, pp 95–109, 1992; Haldar and Vitányi in J ACM 49(1):101–126, 2002) do not scale well in the number of processes as getting a new timestamp takes at least Ω (n) steps. Moreover, a lower bound by Israeli and Li (Proceedings of the 28th annual IEEE symposium on foundations of computer science (FOCS), pp 371–382, 1987) implies that timestamps need to be represented by Ω (m) bits (provided that no other information is used for comparing the temporal order of events associated with timestamps). We introduce a novel specification, called marker-based timestamping (short: MBT) to which the lower bound does not apply, and which is still suitable for applications. Operation marks the (linearization) point of its execution with marker i, and operation returns a Boolean value, indicating the temporal order of the events marked by markers i and j. We present an efficient linearizable and wait-free single-writer MBT system with m markers where m ≥ n , implemented from a single bounded fetch-and-add object and O (m · n) bounded compare-and-swap objects. The step complexity of each method call is constant, and base objects need only store O (log m) bits. [ABSTRACT FROM AUTHOR]

Copyright of Distributed Computing is the property of Springer Nature and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)