Composite registers. (English) Zbl 0781.68042

We introduce a shared data object, called a composite register, that generalizes the notion of an atomic register. A composite register is an array-like shared data object that is partitioned into a number of components. An operation of a composite 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.
We show that multi-reader, single-writer atomic registers can be used to implement a composite register in which there is only one writer per component. In a related paper, we show how to use the composite register construction of this paper to implement a composite register with multiple writers per component. These two constructions show that it is possible to implement a shared memory that can be read in its entirety in a single snapshot operation, without using mutual exlusion.
Reviewer: James H.Anderson


68N25 Theory of operating systems
68Q55 Semantics in the theory of computing
68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)


Full Text: DOI


[1] Afek Y, Attiya H, Dolev D, Gafni E, Merritt M, Shavit N: Atomic snapshots of shared memory. Proc Ninth Ann Symp Princip Distrib Comp 1–14 (1990). · Zbl 0783.68029
[2] Anderson J: Composite registers. Proc Ninth Ann Symp Princip Distrib Comput, pp 15–30 (1990)
[3] Anderson J: Multi-writer composite registers. Technical Report, Department of Computer Science, The University of Maryland at College Park 1991. Preliminary version available as Technical Report TR.89.26, Department of Computer Sciences, University of Texas at Austin 1989
[4] 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
[5] Anderson J, Gouda M: A criterion for atomicity. Formal Asp Comput: Int J Formal Meth 4(3):273–298 (1992) · Zbl 0746.68057 · doi:10.1007/BF01212305
[6] Anderson J, Grošelj B: Pseudo read-modify-write operations: bounded wait-free implementations. Proc. Fifth Int Workshop Distrib Alg. Lect Notes Comput Sci vol 579 Springer, Berlin Heidelberg New York 1991, pp 52–70 1991. (Expanded version to appear in Sci Comput Program)
[7] Aspnes J, Herlihy M: Wait-free data structures in the asynchronous PRAM model. Proc Second Ann ACM Symp Parallel Archit Alg (July 1990)
[8] 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 entitled: A proof Technique for Register Atomicity, appeared in: Proc Eighth Conf Found Softw Techn Theor Comput Sci. Lect Notes Comput Sci vol 338 Springer, Berlin Heidelberg New York 1988, pp 286–303
[9] Bloom B: Constructing two-writer atomic registers. IEEE Trans Comput 37(12):1506–1514 (1988) · Zbl 0663.68034 · doi:10.1109/12.9729
[10] Burns J, Peterson G: Constructing multi-reader atomic values from non-atomic values. Prox Sixth Ann Symp Princip Distrib Comput 222–231 (1987)
[11] Chandy K, Misra J: Parallel program design: a foundation, Addison-Wesley 1988 · Zbl 0717.68034
[12] Chor B, Israeli A, Li M: On processor coordination using asynchronous hardware. Princip Sixth Ann Symp Princip Distrib Comput 86–97 (1987)
[13] Courtois P, Heymans F, Parnas D: Concurrent control with readers and writers. Commun ACM 14(10): pp 667–668 (1971) · doi:10.1145/362759.362813
[14] Herlihy M: Wait-free synchronization. ACM Trans Program Lang Syst 13(1):124–149 (1991) · Zbl 1314.68380 · doi:10.1145/114005.102808
[15] Herlihy M, Wing J: Linearizability: a correctness condition for concurrent objects. ACM Trans Program Lang Syst 12(3):463–492
[16] Israeli A, Li M: Bounded Time-Stamps. Proc 28th IEEE Symp Found Comput Sci 371–382 (1987)
[17] Kirousis L, Kranakis E, Vitanyi P: Atomic multireader register. Proc Second Int Workshop Distrib Comput, Lect Notes Comput Sci vol 312. Springer, Berlin Heidelberg New York, pp 278–296 (1987)
[18] Lamport L: Concurrent reading and writing. Commun ACM 20(11):806–811 (1977) · Zbl 0361.68091 · doi:10.1145/359863.359878
[19] Lamport L: On interprocess communication, parts I and II. Distrib Comput 1:77–101 (1986) · Zbl 0598.68022 · doi:10.1007/BF01786227
[20] Li M, Tromp J, Vitanyi P: How to construct wait-free variables. Proc Int Colloq Autom Lang Program. Lect Notes Comput Sci vol 372 (1989). Springer, Berlin Heidelberg New York 1989, pp 488–505
[21] Loui M, Abu-Amara H: Memory requirements for agreement among unreliable asynchronous processes. Adv Comput Research. JAI Press 1987, pp 163–183
[22] Misra J: Axioms for memory access in asynchronous hardware systems. ACM Trans Program Lang Syst 8(1):142–153 (1986) · Zbl 0593.68017 · doi:10.1145/5001.5007
[23] Newman-Wolfe R: A protocol for wait-free, atomic, multireader shared variables. Proc Sixth Ann Symp Princip Distrib Comput 232–248 (1987)
[24] Peterson G: Concurrent reading while writing. ACM Trans Program Lang Syst, 5:46–55 (1983) · Zbl 0498.68010 · doi:10.1145/357195.357198
[25] Peterson G, Burns J: Concurrent reading while writing II: the multi-writer case. Proc 28th Ann Symp Found Comput Sci, pp 383–392 (1987)
[26] Singh A, Anderson J, Gouda M: The elusive atomic register, revisited. Proc Sixth Ann Symp Princip Distrib Comput 206–221 (1987) · Zbl 0806.68025
[27] Tromp J: How to construct an atomic variable. Proc Third Int Workshop Distrib Alg, Lect Notes Comput Sci vol 392. Springer: Berlin Heidelberg New York 1989, pp 292–302
[28] Vitanyi P, Awerbuch B: Atomic shared register access by asynchronous hardware. Proc 27th IEEE Symp Found Comput Sci, 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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.