Efficient Bounded Timestamping from Standard Synchronization Primitives
Date
2024-04-25
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Timestamping systems are at the core of many solutions to fundamental problems in distributed algorithms [2, 4, 11, 13, 15, 22, 25, 27], and are well-studied. These systems allow processes to determine the temporal ordering of events by assigning a timestamp to each event and defining an ordering on the timestamps that corresponds to the temporal order of events. Israeli and Li [19] were the first to formalize a variation of these systems, called bounded timestamping systems (BTS), wherein the domain of timestamps is finite. They established a crucial lower bound that implies any BTS implementation, where the values of the timestamps assigned to events are sufficient to determine the temporal order of events, requires ฮฉ(๐) bits to represent a timestamp. Existing BTS implementations [3, 6โ8, 12, 20] have ฮฉ(๐) step complexity and use registers of size ฮฉ(๐) bits. This thesis introduces a novel specification for a bounded times- tamping system called marker based timestamping (MBT), which has a more efficient implementation than all prior BTS implementations and is still practical. An MBT object keeps track of ๐ markers where each marker belongs to a process and each process has at least one marker. It provides two functionalities: mark(๐) operation to mark the current point in time with marker ๐, and isEarlier(๐, ๐) to determine the temporal order of the events marked by markers ๐ and ๐. Note that the lower bound of Israeli and Li does not apply to an MBT object. We present a linearizable, wait-free MBT implementation with constant step complexity from ๐(๐ ยท ๐) Compare-And-Swap (CAS) objects and a single bounded Fetch-And-Add (FAA) object, where each base object stores only ๐(log ๐) bits.
Description
Keywords
Theory of computation, Shared memory algorithms, Bounded Timestamping
Citation
Jamadi, A. (2024). Efficient bounded timestamping from standard synchronization primitives (Master's thesis, University of Calgary, Calgary, Canada). Retrieved from https://prism.ucalgary.ca.