Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 20 of 30 for “"wait free"”.
-
Dynamic wait-free atomic snapshot
Efficiently implementing wait-free atomic snapshot objects is one of the core problems in the shared memory model of the theory of distributed computing. An atomic snapshot object gives users access to a set of n shared registers and two types of operations to perform on them. One of the …
-
A Space-Optimal Randomized Wait-Free Lock
… 28, 42]. This thesis presents a new randomized wait-free lock. The algorithm is adaptive to contention, uses constant space, achieves near-optimal expected step complexity and is simple to implement. We assume idempotency of critical section code, based on the works of Ben-David, Blelloch, and …
-
Multiprocessor-safe Wait-free Queue in RTSJ
Currently, most computer systems are running on multiprocessors (or multicores). Moreover, the number of cores inside the processor are expected to increase. To be able to utilise the increased computational power in these systems, developers are enforced to expose more parallelism within their …
-
Understanding the wait-free set-consensus partial order
We present a complete characterization of the Set Consensus Partial Order, a refinement of the Consensus Hierarchy of Herlihy. We define the (n, k )-set consensus problem as the k-set consensus problem for n processors. We then answer the question of whether an (n, k)-set consensus object (an …
-
Concurrent Localized Wait-Free Operations on a Red Black Tree
… type of self-balancing binary search tree. Some wait-free algorithms have been proposed for concurrently accessing and modifying a red-black tree from multiple threads in shared memory systems. Most algorithms presented utilize the concept of a "window", and are entirely top-down implementations. …
-
A Wait-free Queue with Poly-logarithmic Worst-case Step Complexity
In this work, we introduce a novel linearizable wait-free queue implementation. Linearizability and lock-freedom are standard requirements for designing shared data structures. To the best of our knowledge, all of the existing linearizable lock-free queues in the literature have a common problem in …
-
The Design, Implementation, and Refinement of Wait-Free Algorithms and Containers
… of progress provide safety properties and freedom from many hazards, such as dead-lock, live-lock, and thread starvation. In addition to the safety concerns, the fine-grained synchronization used in implementing these algorithms promises to provide scalable performance in massively parallel …
-
The Weakest Failure Detector for Solving Wait-Free, Eventually Bounded-Fair Dining Philosophers
… dining variant is defined by three properties: wait-freedom, eventual weak exclusion, and eventual bounded fairness. Wait-freedom guarantees that every correct hungry process eventually enters its critical section, regardless of process crashes. Eventual weak exclusion guarantees that every …
-
Utility Accrual Real-Time Scheduling and Synchronization on Single and Multiprocessors: Models, Algorithms, and Tradeoffs
… consider non-blocking synchronization including wait-free and lock-free synchronization. We present a buffer-optimal, scheduler-independent wait-free synchronization protocol (the first such), and develop wait-free versions of RUA and DASA. We also develop their lock-free versions, and upper …
-
Strongly Linearizable Implementations of Fundamental Primitives
… adversary model [1]. We devise several new lock-free strongly linearizable implementations from atomic registers. In particular, we give the first strongly linearizable lock-free snapshot implementation that uses bounded space. This improves on the unbounded space solution of Denysyuk and Woelfel …
-
Practical Dynamic Transactional Data Structures
… progress. In this work, we present the first wait-free hash map which allows a large number of threads to concurrently insert, get, and remove information. Wait-freedom means that all threads make progress in a finite amount of time --- an attribute that can be critical in real-time …
-
Classifications of Asynchronous Shared Memory Objects
… object’s ability to implement other objects in a wait-free manner. The first candidate for such a characterization was the consensus number of an object [24]. But a characterization based on consensus numbers is not precise: there are pairs of objects with the same consensus number that are not …
-
Towards Efficient Autonomous Vehicle Systems: A Multi-Layer Approach
… Combined-DBP-TCCP (PCDT) protocol enables wait-free multicore data communication with configurable buffer strategies tailored to task timing requirements. Two optimization strategies, priority assignment with preemption thresholds (PA-MBTT) and wait-free-aware task partitioning (WFAP+), …
-
On the Space Complexity of Colourless Tasks
… algorithm (including any randomized wait-free algorithm) into an obstruction-free algorithm that uses the same number of registers. This result extends to algorithms using any finite number of deterministic objects that support read operations. Hence, we can focus on proving lower …
-
Constant-RMR Implementations of CAS and Other Synchronization Primitives Using Read and Write Operations
… Our implementations are blocking, rather than wait-free: they ensure progress provided all processes that invoke the implemented primitive are live. Our results imply that any algorithm using read and write operations, comparison primitives and load-linked/store-conditional, can be simulated by …
-
Multi-Valued Register Simulations
… operations on them. In this thesis, we study the wait-free simulations of shared read-write registers using weaker shared registers, for two consistency conditions regularity and atomicity. We propose an algorithm which is a hybrid of the existing tree algorithm and the clique algorithm such that …
-
Bipartite Double-Word Compare-and-Swap
… hardware. In this research, we implement a lock-free linearizable bipartite double-word compare-and-swap operation. This operation can be used on its own as a restricted version of the double-word compare-and-swap operation. However, the most significant feature of our algorithm is that our …
-
Topological characterization of simplex agreement
… charakterisieren wir die Lösbarkeit im wait-free und im t-resilient Modell anhand topologischer Zusammenhangseigenschaften von A. Da Clique Agreement auf einem Graphen G äquivalent zu Simplex Agreement auf dem zugehörigen Kliquenkomplex K(G) ist, ergeben sich daraus unmittelbar …
-
Techniques for enhancing parallelism in mechanisms that automatically execute sequential code in concurrent environments
… allow for increased parallelism.Wait-freedom is a well-known progress property which ensures that each process completesits execution, even when other processes run at arbitrary speeds or crash. Waitfreedomis highly desirable because implementations ensuring this property are …
Page 1 of 2