Bounded delay for a free address (Q1901690)

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.