Abstract
Multireader shared registers are basic objects used as communication medium in asynchronous concurrent computation. We propose a surprisingly simple and natural scheme to obtain several wait-free constructions of bounded 1-writer multireader registers from atomic 1-writer 1-reader registers, that is easier to prove correct than any previous construction. Our main construction is the first symmetric pure timestamp one that is optimal with respect to the worst-case local use of control bits; the other one is optimal with respect to global use of control bits; both are optimal in time.
This work was supported in part by the EU fifth framework project QAIP, IST-1999-11234, the NoE QUIPROCONE IST-1999-29064, the ESF QiT Programmme, and the EU Fourth Framework BRA NeuroCOLT II Working Group EP 27150.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
J. Anderson, Multi-Writer Composite Registers, Distributed Computing, 7:4(1994), 175–195.
K. Abrahamson, On achieving consensus using a shared memory. In Proc. 7th ACM Symp. Principles Distribut. Comput., 1988, 291–302.
B. Bloom, Constructing two-writer atomic registers. IEEE Trans. on Computers, 37(1988), 1506–1514.
J.E. Burns and G.L. Peterson, Constructing multi-reader atomic values from non-atomic values. In Proc. 6th ACM Symp. Principles of Distributed Computing. 1987, 222–231.
D. Dolev and N. Shavit, Bounded concurrent time-stamp systems are constructible. Siam J. Computing, 26:2(1997), 418–455.
C. Dwork and O. Waarts, Simple and efficient bounded concurrent timestamping and the traceable use abstraction. J. Assoc. Comput. Mach., 46:5(1999), 633–666.
C. Dwork, M. Herlihy, S. Plotkin and O. Waarts, Time-Lapse snapshots. SIAM J. Computing, 28:5(1999), 1848–1874.
R. Gawlick, N.A. Lynch, and N. Shavit, Concurrent timestamping made simple. In Proc. Israeli Symp. Theory Comput. and Systems, LNCS 601, Springer-Verlag, 1992, 171–183.
S. Haldar and K. Vidyasankar, Counterexamples to a one writer multireader atomic shared variable construction of Burns and Peterson. ACM Oper. Syst. Rev., 26:1(1992), 87–88.
S. Haldar and K. Vidyasankar, Constructing 1-writer multireader multivalued atomic variables from regular variables. J. Assoc. Comput. Mach., 42:1(1995), 186–203.
S. Haldar and K. Vidyasankar, Buffer-optimal constructions of 1-writer multireader multivalued atomic shared variables. J. Parallel Distr. Comput., 31:2(1995), 174–180.
S. Haldar and K. Vidyasankar, Simple extensions of 1-writer atomic variable constructions to multiwriter ones. Acta Informatica, 33:2(1996), 177–202.
S. Haldar and P. Vitanyi, Bounded concurrent timestamp systemss using vector clocks, J. Assoc. Comp. Mach., 49:1(2002), 101–126.
M. Herlihy and J. Wing, Linearizability: A correctness condition for concurrent objects. A CM Trans. Progr. Lang. Syst., 12:3(1990), 463–492.
A. Israeli and M. Li, Bounded time-stamps. Distributed Computing, 6(1993), 205–209.
A. Israeli and M. Pinhasov, A concurrent time-stamp scheme which is linear in time and space. In Proc. 6th Intn’l Workshop Distribut. Alg., LNCS 647, Springer-Verlag, Berlin, 1992, 95–109.
A. Israeli and A. Shaham, Optimal multi-writer multireader atomic register. In Proc. 11th ACM Symp. Principles. Distr. Comput., 1992, 71–82.
L.M. Kirousis, E. Kranakis, and P.M.B. Vitányi, Atomic multireader register. In Proc. 2nd Intn’l Workshop Distr. Alg.. LNCS 312, Springer-Velag, Berlin, 1987, 278–296.
L. Lamport, On interprocess communication — Part I: Basic formalism, Part II: Algorithms. Distributed Computing, 1:2(1986), 77–101.
M. Li and P.M.B. Vitányi, Optimality of wait-free atomic multiwriter variables, Inform. Process. Lett., 43:2(1992), 107–112.
M. Li, J.T. Tromp, and P.M.B. Vitányi, How to share concurrent wait-free variables. J. Assoc. Comput. Mach., 43:4(1996), 723–746.
N. Lynch, Distributed Algorithms, Morgan Kaufmann, 1997.
G.L. Peterson, Concurrent reading while writing. ACM Trans. Progr. Lang. Systems, 5:1(1983), 56–65.
G.L. Peterson and J.E. Burns, Concurrent reading while writing II: The multiwriter case. In Proc. 28th IEEE Symp. Found. Comput. Sci., 1987, 383–392.
R. Schaffer, On the correctness of atomic multiwriter registers. Report MIT/LCS/TM-364, 1988.
A.K. Singh, J.H. Anderson and M.G. Gouda, The elusive atomic register. J. Assoc. Comput. Mach., 41:2(1994), 311–339.
R. Newman-Wolfe, A protocol for wait-free, atomic, multi-reader shared variables. In Proc. 6th ACM Symp. Princples Distribut. Comput., 1987, 232–248.
P.M.B. Vitányi and B. Awerbuch, Atomic shared register access by asynchronous hardware. In Proc. 27th IEEE Symp. Found. Comput. Sci., 1986, 233–243. Errata: Ibid., 1987, 487.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Vitányi, P. (2002). Simple Wait-Free Multireader Registers. In: Malkhi, D. (eds) Distributed Computing. DISC 2002. Lecture Notes in Computer Science, vol 2508. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-36108-1_8
Download citation
DOI: https://doi.org/10.1007/3-540-36108-1_8
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-00073-0
Online ISBN: 978-3-540-36108-4
eBook Packages: Springer Book Archive