Summary
Acomposite register is an array-like shared data object that is partitioned into a number of components. An operation of such a register either writes a value to a single component, or reads the values of all components. A composite register reduces to an ordinary atomic register when there is only one component. In this paper, we show that a composite register with multiple writers per component can be implemented in a wait-free manner from a composite register with a single writer per component. It has been previously shown that registers of the latter kind can be implemented from atomic registers without waiting. Thus, our results establish that any composite register can be implemented in a wait-free manner from atomic registers. We show that our construction has comparable space compexity and better time complexity than other constructions that have been presented in the literature.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Afek Y, Attiya H, Dolev D, Gafni E, Merritt M, Shavit N: Atomic snapshots of shared memory. Proceedings of the Ninth Annual Symposium on Principles of Distributed Computing 1990, pp 1–14
Anderson J: Composite registers (extended abstract). Proceedings of the Ninth Annual Symposium on Principles of Distributed Computing 1990, pp 15–30
Anderson J: Composite Registers. Distrib Comput 6: 141–154 (1993). First appeared as Technical Report TR.89.25, Department of Computer Sciences, University of Texas at Austin 1989
Anderson J: Multi-writer composite registers. Technical Report, Department of Computer Science, The University of Maryland at College Park 1991. First appeared as Technical Report TR.89.26, Department of Computer Sciences, University of Texas at Austin 1989
Anderson J, Gouda M: The virtue of patience: concurrent programming with and without waiting. Technical Report TR.90.23, Department of Computer Sciences, The University of Texas at Austin 1990
Anderson J, Gouda M: A criterion for atomicity. Formal Asp Comput 4 (3): 273–298 (1992)
Anderson J, Grošelj B: Pseudo read-modify-write operations: bounded wait-free-implementations. Proceedings of the Fifth International Workshop on Distributed Algorithms, Lect Notes Comput Sci 579: 52–70 (1991)
Anderson J, Grošelj B: Beyond atomic registers: bounded waitfree implementations of non-trivial objects. Sci Comput Program 19 (3): 197–237 (1992)
Anderson J, Moir M: Towards a necessary and sufficient condition for wait-free synchronization. Proceedings of the Seventh International Workshop on Distributed Algorithms. Lect Notes Comput Sci 725: 39–53 (1993)
Aspnes J, Herlihy M: Wait-free data structures in the asynchronous PRAM model. Proceedings of the Second Annual ACM Symposium on Parallel Architectures and Algorithms 1990, pp 340–349
Attiya H, Rachman O: Atomic snapshots inO(n logn) operations. Proceedings of the 12th Annual Symposium on Principles of Distributed Computing 1993, pp 29–40
Awerbuch B, Kirousis L, Kranakis E, Vitanyi P: On proving register atomicity. Report CS-R8707, Centre for Mathematics and Computer Science, Amsterdam, 1987. A shorter version appeared as: A proof technique for register atomicity. Proceedings of the Eighth Conference on Foundations of Software Techniques and Theoretical Computer Science. Lect Notes Comput Sci 338: 286–303 (1988)
Bloom B: Construction two-writer atomic registers. IEEE Trans Comput 37 (12): 1506–1514 (1988)
Burns J, Peterson G: Construction multi-reader atomic values from non-atomic values. Proceedings of the Sixth Annual Symposium on Principle of Distributed Computing 1987, pp 222–231
Chandy K, Misra J: Parallel program design: a foundation. Addison-Wesley, New York 1988
Chor B, Israeli A, Li M: On Processor coordination using asynchronous hardware. Principles of the Sixth Annual Symposium on Principles of Distributed Computing 1987, pp 86–97
Courtois P, Heymans F, Parnas D: Concurrent control with readers and writers. Commun ACM 14 (10): 667–668 (1971)
Herlihy M: Wait-Free Synchronization. ACM Trans Program Lang Syst 13 (1): 124–149 (1991)
Herlihy M, Wing J: Linearizability: a correctness condition for concurrent objects. ACM Trans Program Lang Syst 12 (3): 463–492 (1990)
Israeli A, Li M: Bounded time-stamps. Proceedings of the 28th IEEE Symposium on Foundations of Computer Science 1987, pp 371–382
Kirousis L, Kranakis E, Vitanyi P: Atomic multireader register. Proceedings of the Second International Workshop on Distributed Computing. Lect Notes Comput Sci 312: 278–296 (1987)
Kirousis L, Spirakis P, Tsigas P: Simple atomic snapshots: a solution with unbounded time stamps. Proceedings of the International Conference on Computing and Information. Lect Notes Comput Sci 497: 582–587 (1991)
Kirousis L, Spirakis P, Tsigas P: Reading many variables in one atomic operation: solutions with linear or sublinear complexity. Proceedings of the Fifth International Workshop on Distributed Algorithms. Lect Notes Comput Sci 579: 229–241 (1991)
Lamport L: Concurrent reading and writing. Commun ACM 20 (11): 806–811 (1977)
Lamport L: On interprocess communication, Part I and II. Distrib Comput 1: 77–101 (1986)
Li M, Tromp J, Vitanyi P: How to construct wait-free variables. Proceedings of International Colloquium on Automata, Languages, and Programming. Lect Notes Comput Sci 372: 488–505 (1989)
Loui M, Abu-Amara H: Memory requirement for agreement among unreliable asynchronous processes. Adv Comput Res 4: 163–183 (1987)
Misra J: Axioms for memory access in asynchronous hardware systems. ACM Trans Program Lang Syst 8 (1): 142–153 (1986)
Newman-Wolfe R: A protocol for wait-free, atomic, multi-reader shared variables. Proceedings of the Sixth Annual Symposium on Principles of Distributed Computing 1987, pp 232–248
Peterson G: Concurrent reading while writing. ACM Trans Program Lang Syst 5: 46–55 (1983)
Peterson G, Burns J: Concurrent reading while writing II: the multi-writer case. Proceedings of the 28th Annual Symposium on Foundations of Computer Science 1987, pp 383–392
Singh A, Anderson J, Gouda M: The elusive atomic register, revisited. Proceedings of the Sixth Annual Symposium on Principles of Distributed Computing 1987, pp 206–221. Expanded version to appear in Journal of the ACM
Tromp J: How to construct an atomic variable. Proceedings of the Third International Workshop on Distributed Algorithms. Lect Notes Comput Sci 392: 292–302 (1989)
Vitanyi P, Awerbuch B: Atomic shared register access by asynchronous hardware. Proceedings of the 27th IEEE Symposium on the Foundations of Computer Science 1986, pp 233–243
Author information
Authors and Affiliations
Additional information
James H. Anderson received the B.S. degree in Computer Science from Michigan State University in 1982, the M.S. degree in Computer Science from Purdue University in 1983, and the Ph.D. degree in Computer Sciences from the University of Texas at Austin in 1990. He recently joined the Computer Science Department at the University of North Carolina at Chapel Hill, where he is now an Assistant Professor. Prior to joining the University of North Carolina, he was an Assistant Professor of Computer Science for three years at the University of Maryland at College Park. Professor Anderson's main research interests are within the area of concurrent and distributed computing. His current interests primarily involve the implementation of resilient and scalable synchronization mechanisms.
Much of the work described herein was completed while the author was with the University of Texas at Austin and the University of Maryland at College Park. This work was supported at the University of Texas by ONR Contract N00014-89-J-1913, and at the University of Maryland by NSF Contract CCR 9109497 and by an award from the University of Maryland General Research Board
Rights and permissions
About this article
Cite this article
Anderson, J.H. Multi-writer composite registers. Distrib Comput 7, 175–195 (1994). https://doi.org/10.1007/BF02280833
Received:
Accepted:
Issue Date:
DOI: https://doi.org/10.1007/BF02280833