Optimal multi-writer multi-reader atomic register

ABSTRACT

Two implementations of a multi-writer, multi-reader, atomic register are presented. The physical registers used by the first implementation are single-writer, multi-reader, atomic registers; the physical registers used by the second implementation are single-reader, single-writer, atomic registers. Both implementations are optimal with respect to the two most important complexity criteria: In both implementation the space complexity is logarithmic, thus matching the lower bound proven by Cori and Sopena; and the time complexity is linear, thus matching the obvious lower bound. These implementations improve upon the space complexity of all previous implementations in their respective classes, by an exponential factor.

REFERENCES

• AB91: U. Abraham, "MultiWriter Atomic Registers and bounded timestamps," preprint.
• CS90: R. Cori and E. Sopena "Some combinatorial aspects of Time Stamps Systems," submitted to J. Of Algorithms.
• IL87: A. israeli, and M. Li, "Bounded Time-Stamps," Proceedings of the 28th Annum Symposium on Foundations of Computer Science, 1987, pp. 371-382.
• ILV87: A. Israeli, M. Li, and P. Vitanyi, "Simple Multireader registers using Time-Stamp schemes," Report no. CS-R8758 Center for Mathematics and Computer Science, Amsterdam, Holland, November 1987.
• ITV92: A. Israeli, J. Tromp, and P.M.B. Vitanyi, personal communication.
• La86a: L. Lamport, "On Interprocess Communication. Part I: Basic Formalism,'' Distributed Computing 1, 2 1986, pp. 77-85.
• La86b: L. Lamport, "On Interprocess Communication. Part II: Algorithms," Distributed Computing 1, 2 1986, pp. 86-101.
• LTV90: Ming Li , John Tromp , Paul M. B. Vitányi, How to share concurrent wait-free variables, Journal of the ACM (JACM), v.43 n.4, p.723-746, July 1996 [doi>10.1145/234533.234556]
• LV90: M. Li and P.M.B. Vit~nyi, "Optimality of Wait-Free Atomic Multiwriter Variables," Submitted to information Processing Letters 1990. Techn. Rept. CS-R9128, CWI, June 1991.
• PB87: G.L. Peterson and J.E. Burns, "Concurrent reading while writing II: the multiwriter case", 28th Annual IEEE Symp. on Foundations of Computer Science, 1987, pp. 383- 392.
• Sc89: R.W. Schaffer, "On the Correctness of Atomic Multi-Writer Registers", preprint.
• VA86: P. Vitanyi, and B. Awerbuch, "Atomic Shared Register Access by Asynchronous Hardware," Proceedings of the 27th Annum Symposium on Foundations of Computer Science, 1986, pp.233-243.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees

Additional Classification:
  B. Hardware
  B.5 REGISTER-TRANSFER-LEVEL IMPLEMENTATION
  B.6 LOGIC DESIGN

General Terms:
Design