Browsing by Author "Jamadi, Ali"

Now showing 1 - 2 of 2
  • Thumbnail Image
    ItemOpen Access
    Efficient Bounded Timestamping from Standard Synchronization Primitives
    (2023) Bashari, Benyamin; Jamadi, Ali; Woelfel, Philipp
    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.
  • Thumbnail Image
    ItemOpen Access
    Efficient Bounded Timestamping from Standard Synchronization Primitives
    (2024-04-25) Jamadi, Ali; Woelfel, Philipp; Woelfel, Philipp; Jayanti, Prasad; Cockett, Robin; Denzinger, Jorg
    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.