Progress-space tradeoffs in single-writer memory implementations
From MaRDI portal
Abstract: Most algorithms designed for shared-memory distributed systems assume the single-writer multi-reader (SWMR) setting where each process is provided with a unique register readable by all. In a system where computation is performed by a bounded number n of processes coming from a very large (possibly unbounded) set of potential participants, the assumption of a SWMR memory is no longer reasonable. If only a bounded number of multi-writer multi-reader (MWMR) registers are provided, we cannot rely on an a priori assignment of processes to registers. In this setting, simulating SWMR memory, or equivalently, ensuring stable writing (i.e., every written value persists in the memory), is desirable. In this paper, we propose a SWMR simulation that adapts the number of MWMR registers used to the desired progress condition. For any given k from 1 to n, we present an algorithm that uses only n+k-1 registers to simulate a k-lock-free SWMR memory. We also give a matching lower bound of n+1 registers required for the case of 2-lock-freedom, which supports our conjectures that the algorithm is space-optimal. Our lower bound holds for the strictly weaker progress condition of 2-obstruction-freedom, which suggests that the space complexity for k-obstruction-free and k-lock-free SWMR simulations might coincide.
Recommendations
- Bounds on the Costs of Multivalued Register Implementations
- Step optimal implementations of large single-writer registers
- A tight time lower bound for space-optimal implementations of multi-writer snapshots
- Bounds on the shared memory requirements for long-lived \& adaptive objects (extended abstract)
- Allocate-on-use space complexity of shared-memory algorithms
Cites work
- A tight space bound for consensus
- Anonymous obstruction-free \((n,k)\)-set agreement with \(n-k+1\) atomic read/write registers
- Atomic snapshots of shared memory
- Bounds on shared memory for mutual exclusion
- Contention-Sensitive Data Structures and Algorithms
- Linear space bootstrap communication schemes
- On the space complexity of set agreement?
- Renaming in an asynchronous environment
- Safety-liveness exclusion in distributed computing
- Time and space lower bounds for non-blocking implementations (preliminary version)
- Time-space tradeoffs for implementations of snapshots
- Wait-free solvability of colorless tasks in anonymous shared-memory model
This page was built for publication: Progress-space tradeoffs in single-writer memory implementations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3300806)
