Time and space optimal implementations of atomic multi-writer register. (English) Zbl 1082.68017

Summary: This paper addresses the wide gap in space complexity of atomic, multi-writer, multi-reader register implementations. While the space complexity of all previous implementations is linear, the lower bounds are logarithmic. We present three implementations which close this gap: The first implementation is sequential and its role is to present the idea and data structures used in the second and third implementations. The second and third implementations are both concurrent, the second uses multi-reader physical registers while the third uses single-reader physical registers. Both the second and third implementations are optimal with respect to the two most important complexity criteria: Their space complexity is logarithmic and their time complexity is linear.


68N25 Theory of operating systems
68P05 Data structures
Full Text: DOI


[1] Afek, Y.; Attiya, H.; Dolev, D.; Gafni, E.; Merritt, M.; Shavit, N., Atomic snapshots of shared memory, J. ACM, 40, 4, 873-890, (1993) · Zbl 0783.68029
[2] Abraham, U., On interprocess communication and the implementation of a multi-writer atomic registers, Theor. comput. sci., 149, 257-298, (1995) · Zbl 0874.68121
[3] Cori, R.; Sopena, E., Some combinatorial aspects of time stamp systems, Eur. J. combin., 14, 95-102, (1993) · Zbl 0771.05043
[4] Dolev, D.; Shavit, N., Bounded concurrent time-stamping, SIAM J. comput., 26, 2, 418-455, (1997) · Zbl 0874.68138
[5] M.P. Herlihy, Impossibility and universality results for wait-free synchronization, in: Proceedings of the 7th ACM Symposium on Principles of Distributed Computing, 1988, pp. 276-290
[6] M. Herlihy, J. Wing, Axioms for concurrent objects, in: 14th ACM Symposium on Principles of Programming Languages, 1987, pp. 13-26
[7] Israeli, A.; Li, M., Bounded time-stamps, Distrib. comput., 6, 4, 205-209, (1993) · Zbl 0776.68018
[8] A. Israeli, J. Tromp, P.M.B. Vitányi, personal communication
[9] Lamport, L., On interprocess communication. part I: basic formalism, Distrib. comput., 1, 2, 77-85, (1986) · Zbl 0598.68022
[10] Lamport, L., On interprocess communication. part II: algorithms, Distrib. comput., 1, 2, 86-101, (1986) · Zbl 0598.68023
[11] N. Lynch, M. Tuttle, Hierarchical correctness proofs for distributed algorithms, in: Proceedings of the 6th ACM Symposium on Principles of Distributed Computing, 1988, pp. 137-151
[12] Li, M.; Tromp, J.; Vitányi, P.M.B., How to share concurrent wait-free variables, J. ACM, 43, 107-112, (1992)
[13] Li, M.; Vitányi, P.M.B., Optimality of wait-free atomic multiwriter variables, Inform. process. lett., 43, 107-112, (1992) · Zbl 0825.68380
[14] Misra, J., Axioms for memory access in asynchronous hardware systems, ACM trans. progr. lang. syst., 8, 1, 142-153, (1986) · Zbl 0593.68017
[15] Peterson, G.L., Concurrent Reading while writing, ACM trans. progr. lang. syst., 5, 1, 46-55, (1983) · Zbl 0498.68010
[16] G.L. Peterson, J.E. Burns, Concurrent reading while writing II: the multiwriter case, in: 28th Annual IEEE Symposium on Foundations of Computer Science, 1987, pp. 383-392
[17] R.W. Schaffer, On the correctness of atomic multi-writer registers, Technical Report MIT/LCS/TM-364, Laboratory for Computer Science, MIT
[18] Tromp, J., On update-last schemes, Parallel process. lett., 44, 1, 25-28, (1993)
[19] P. Vitányi, B. Awerbuch, Atomic shared register access by asynchronous hardware, in: Proceedings of the 27th Annual Symposium on Foundations of Computer Science, 1986, pp. 233-243
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.