AbstractSharing data between multiple asynchronous users -- each of which can atomically read and write the data -- is a feature that may help to increase the amount of parallelism in distributed systems. An algorithm implementing this feature is presented. The main construction of an n-user atomic variable directly from single-writer, single-reader atomic variables uses O(n) control bits and O(n) accesses per Read/Write running in O(1) parallel time.
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; B.4.3 [Input/Output and Data Communications]: Interconnections (subsystems); D.4.1 [Operating Systems]: Process Management; D.4.4 [Operating Systems]: Communications Management
General Terms: Management
Additional Key Words and Phrases: Atomicity, concurrent reading and writing, multi-writer, shared variable (register)
Selected papers that cite this one
- Danny Dolev and Nir Shavit. Bounded concurrent time-stamping. SIAM Journal on Computing, 26(2):418-455, April 1997.
Selected references
- Danny Dolev and Nir Shavit. Bounded concurrent time-stamp systems are constructible. In Proceedings of the Twenty First Annual ACM Symposium on Theory of Computing, pages 454-466, Seattle, Washington, 15-17 May 1989.
- Cynthia Dwork and Orli Waarts. Simple and efficient bounded concurrent timestamping or bounded concurrent timestamp systems are comprehensible! In Proceedings of the Twenty-Fourth Annual ACM Symposium on the Theory of Computing, pages 655-666, Victoria, British Columbia, Canada, 4-6 May 1992.
- 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.
- Maurice Herlihy and Jeannette M. Wing. Linearizability: A correctness condition for concurrent objects. ACM Transactions on Programming Languages and Systems, 12(3):463-492, July 1990.
- Amos Israeli and Ming Li. Bounded time-stamps (extended abstract). In 28th Annual Symposium on Foundations of Computer Science, pages 371-382, Los Angeles, California, 12-14 October 1987. IEEE.
- Nancy Lynch and Frits Vaandrager. Forward and backward simulations: I. Untimed systems. Information and Computation, 121(2):214-233, September 1995.
- Gary L. Peterson. Concurrent reading while writing. ACM Transactions on Programming Languages and Systems, 5(1):46-55, January 1983.
- Gary L. Peterson and James E. Burns. Concurrent reading while writing II: The multi-writer case. In 28th Annual Symposium on Foundations of Computer Science, pages 383-392, Los Angeles, California, 12-14 October 1987. IEEE.
- Paul M. B. Vitányi and Baruch Awerbuch. Atomic shared register access by asynchronous hardware (detailed abstract). In 27th Annual Symposium on Foundations of Computer Science, pages 233-243, Toronto, Ontario, Canada, 27-29 October 1986. IEEE.