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 <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="446_2025_478_Article_IEq1.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="35" /> </InlineMediaObject> <EquationSource Format="TEX">$\Omega (n)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="normal">Ω</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> 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 <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="446_2025_478_Article_IEq2.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="40" /> </InlineMediaObject> <EquationSource Format="TEX">$\Omega (m)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="normal">Ω</mi> <mo stretchy="false">(</mo> <mi>m</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> 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 <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="MediaObjects/446_2025_478_Figa_HTML.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="120" Type="Linedraw" Width="66" /> </InlineMediaObject> marks the (linearization) point of its execution with marker i, and operation <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="MediaObjects/446_2025_478_Figb_HTML.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="120" Type="Linedraw" Width="128" /> </InlineMediaObject> 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 <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="446_2025_478_Article_IEq3.gif" Format="GIF" Height="15" Rendition="HTML" Resolution="72" Type="Linedraw" Width="51" /> </InlineMediaObject> <EquationSource Format="TEX">$m\ge n$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>m</mi> <mo>≥</mo> <mi>n</mi> </mrow> </math></EquationSource> </InlineEquation>, implemented from a single bounded fetch-and-add object and <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="446_2025_478_Article_IEq4.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="65" /> </InlineMediaObject> <EquationSource Format="TEX">$O(m\cdot n)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <mi>m</mi> <mo>·</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> bounded compare-and-swap objects. The step complexity of each method call is constant, and base objects need only store <InlineEquation ID="IEq5"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="446_2025_478_Article_IEq5.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="65" /> </InlineMediaObject> <EquationSource Format="TEX">$O(\log m)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <mo>log</mo> <mi>m</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> bits.

Efficient bounded timestamping from standard synchronization primitives

期刊论文
发表日期：

2025年4月28日

查看全文

Benyamin Bashari,
Ali Jamadi,
Philipp Woelfel

摘要

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 $\Omega (n)$ $Ω (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 $\Omega (m)$ $Ω (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\ge n$ $m \geq n$ , implemented from a single bounded fetch-and-add object and $O(m\cdot n)$ $O (m \cdot n)$ bounded compare-and-swap objects. The step complexity of each method call is constant, and base objects need only store $O(\log m)$ $O (log m)$ bits.