AbstractA simple wait-free construction for 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. Copyright 1995 by ACM, Inc.
The abstract is also available as a LaTeX file, a DVI file, or a PostScript file.
Categories and Subject Descriptors: B.3.2 [Memory Structures]: Design Styles -- shared memory; B.4.3 [Input/Output and Data Communications]: Interconnections (subsystems) -- asynchronous/synchronous operation; D.1.3 [Programming Techniques]: Concurrent Programming; D.4.1 [Operating Systems]: Process Management; D.4.4 [Operating Systems]: Communications Management -- buffering
General Terms: Algorithms, Theory, Verification
Additional Key Words and Phrases: Nonatomic operation execution, reader and writer, shared variable-safe, regular and atomic, wait-freedom
Selected papers that cite this one
- Ming Li, John Tromp, and Paul M. B. Vitányi. How to share concurrent wait-free variables. Journal of the ACM, 43(4):723-746, July 1996.
- Ariel Orda and Michael Merritt. Efficient test&set constructions for faulty shared memory. Information Processing Letters, 62(1):41-46, 14 April 1997.
Selected references
- James Aspnes, Maurice Herlihy, and Nir Shavit. Counting networks and multi-processor coordination. In Proceedings of the Twenty Third Annual ACM Symposium on Theory of Computing, pages 348-358, New Orleans, Louisiana, 6-8 May 1991.
- Maurice Herlihy, Nir Shavit, and Orli Waarts. Low contention linearizable counting. In 32nd Annual Symposium on Foundations of Computer Science, pages 526-535, San Juan, Puerto Rico, 1-4 October 1991. IEEE.