Journal of the ACM · 1995 · 40 citations · 13 references
ComputingComputer ScienceCompilersFormal MethodsProgramming LanguagesData-flow AnalysisRegular LanguagesAtomic Memory OperationsCorrectness CheckingCorrectness ProofsRegular ExpressionsWait-free AlgorithmsWait-free Data StructuresWait-free Programming
A simple wait-free construction of 1-writer multireader multivalued atomic variable from multireader regular variables is presented in this paper. A key point of the construction is the use of an elegant forwarding technique to overcome the new-old inversion property inherent in regular variables. Another construction, using a different forwarding technique, is also given. This technique is a refinement of one proposed in the literature. Formal correctness proofs for both the constructions are short and easy to follow.
13