Journal of the ACM Bibliography

S. Haldar and K. Vidyasankar. Constructing 1-writer multireader multivalued atomic variable from regular variables. Journal of the ACM, 42(1):186-203, January 1995. [BibTeX entry]

A 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

Selected references


  • Journal of the ACM homepage
  • Bibliography top level
  • Journal of the ACM Author Index
  • Search the HBP database