Browsing by Author "Bashari, Benyamin"
Now showing 1 - 3 of 3
Results Per Page
Sort Options
Item Open Access Adaptive Partial Snapshots with Logarithmic Step Complexity(2021-06-06) Bashari, Benyamin; Woelfel, PhilippThe standard single-writer snapshot type allows processes to obtain a consistent snapshot of an array of n memory locations, each of which can be updated by one of n processes. In almost all algorithms, a Scan() operation returns a linearizable snapshot of the entire array. Under realistic assumptions, where hardware registers do not have the capacity to store many array entries, this inherently leads to a step complexity of Ω(n). In this paper, we consider an alternative version of the snapshot type, where a Scan() operation stores a consistent snapshot of all n memory locations, but does not return anything. Instead, a process can later observe the value of any component of that snapshot using a separate Observe() operation. This allows us to implement the type from fetch-and-increment and compare-and-swap objects, such that Scan() operations have constant step complexity and Update() and Observe() operations have step complexity O(logn).Item Open Access An Efficient Adaptive Partial Snapshot Implementation(2021-10-19) Bashari, Benyamin; Woelfel, Philipp; Woelfel, Philipp; Ruppert, Eric; Jacobson, MichaelIn an asynchronous shared-memory system with n processes, the single-writer snapshot type provides consistent views of an array A of n components, each of which can be updated by one of the processes. Formally, a process p can call Update(v) to write v into A[p], and call Scan() to obtain a view of A. Inherently, under realistic assumptions on the base objects’ size, the specification of this type leads to a lower bound of Ω(n) steps for method Scan(). In some cases, it suffices for a process to take a snapshot of k (1 ≤ k ≤ n) components of A, and thus, taking Ω(n) steps to obtain that snapshot is inefficient when k is small. In this thesis, we provide an implementation of the single-writer adaptive partial snapshot type, which allows a process to take a partial snapshot of k components in O(k log n) steps. We define a new version of Scan() that does not return anything and its behavior is defined in terms of another operation Observe(). An Observe(i) operation by process p returns the value that A[i] had at the point in time of p’s preceding Scan(). We implement a single-writer adaptive partial snapshot object from read-write registers, fetch-and-increment objects, and compare-and-swap objects, such that the step complexity of method Scan() is O(1) and that of methods Update() and Observe() is O(log n).Item Open Access Efficient Bounded Timestamping from Standard Synchronization Primitives(2023) Bashari, Benyamin; Jamadi, Ali; Woelfel, PhilippBounded 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.