The paper treats a problem of concurrent processes that communicate by means of shared variables. The problem is to let \(n\) processes concurrently and repeatedly search for free addresses in a range of \(m\) addresses. The search must be wait-free: a searching process finds an address in a bounded number of steps. Three solutions are presented. The first one has large atomic actions. The second one is only correct if \(m \geq (r + 1) \cdot n\) where \(r\) is the maximum number of used addresses. The third solution is always partially correct. It is wait-free if \(m > r + 2 \cdot n\). This solution has a worst-case waiting time quadratic in \(n\) and an amortized waiting time linear in \(n\), even linear in the number of active processes. Invariants are used to prove the correctness of the algorithms.
- An axiomatic proof technique for parallel programs
- scientific article; zbMATH DE number 50008 (Why is no real title available?)
- scientific article; zbMATH DE number 193479 (Why is no real title available?)
- scientific article; zbMATH DE number 194539 (Why is no real title available?)
- Immediate atomic snapshots and fast renaming
- Renaming in an asynchronous environment
- Wait-free linearization with an assertional proof
This page was built for publication: Bounded delay for a free address
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1901690)
