Long-Lived Test-And-Set Using Bounded Space ⋆
Jaap-Henk Hoepman · 1999
Abstract This paper studies the problem of implementing a shared memory test-and-set object using only shared registers. Our contribution is threefold. First, we present a general framework to allow reasoning about reusing one-shot shared memory objects in the construction of bounded space long-lived objects. Then we derive general theorems about test-andset objects that simplifies reasoning about their implementation. Finally we show the validity of our approach by constructing an n process longlived test-and-set object from n + 1 one-shot test-and-set objects, and proving this construction formally correct. 1