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"”.

  1. 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 …

    manitoba Repository record for Dynamic wait-free atomic snapshot (opens in a new tab)

  2. 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 …

    calgary Repository record for A Space-Optimal Randomized Wait-Free Lock (opens in a new tab)

  3. 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 …

    whiterose Download PDF for Multiprocessor-safe Wait-free Queue in RTSJ (opens in a new tab)

  4. 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 …

    iastate Repository record for Understanding the wait-free set-consensus partial order (opens in a new tab)

  5. 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. …

    unlv Repository record for Concurrent Localized Wait-Free Operations on a Red Black Tree (opens in a new tab) Download PDF for Concurrent Localized Wait-Free Operations on a Red Black Tree (opens in a new tab)

  6. 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 …

    york Repository record for A Wait-free Queue with Poly-logarithmic Worst-case Step Complexity (opens in a new tab)

  7. 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 …

    ucf Repository record for The Design, Implementation, and Refinement of Wait-Free Algorithms and Containers (opens in a new tab)

  8. 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 …

    tamu Repository record for The Weakest Failure Detector for Solving Wait-Free, Eventually Bounded-Fair Dining Philosophers (opens in a new tab)

  9. 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 …

    vt Repository record for Utility Accrual Real-Time Scheduling and Synchronization on Single and Multiprocessors: Models, Algorithms, and Tradeoffs (opens in a new tab)

  10. 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 …

    calgary Repository record for Strongly Linearizable Implementations of Fundamental Primitives (opens in a new tab)

  11. 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 …

    ucf Repository record for Practical Dynamic Transactional Data Structures (opens in a new tab)

  12. 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 …

    toronto-retro Repository record for Classifications of Asynchronous Shared Memory Objects (opens in a new tab)

  13. 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+), …

    vt Repository record for Towards Efficient Autonomous Vehicle Systems: A Multi-Layer Approach (opens in a new tab)

  14. 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 …

    toronto-retro Repository record for On the Space Complexity of Colourless Tasks (opens in a new tab)

  15. 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 …

    toronto-retro Repository record for Constant-RMR Implementations of CAS and Other Synchronization Primitives Using Read and Write Operations (opens in a new tab)

  16. 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 …

    tamu Repository record for Multi-Valued Register Simulations (opens in a new tab)

  17. 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 …

    calgary Repository record for Bipartite Double-Word Compare-and-Swap (opens in a new tab)

  18. 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 …

    humboldt-diss Repository record for Topological characterization of simplex agreement (opens in a new tab)

  19. 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 …

    greece Repository record for Techniques for enhancing parallelism in mechanisms that automatically execute sequential code in concurrent environments (opens in a new tab)

Page 1 of 2