Bounded concurrrent time-stamp systems are constructible

ABSTRACT

Concurrent time stamping is at the heart of solutions to some of the most fundamental problems in distributed computing. Based on concurrent-time-stamp-systems, elegant and simple solutions to core problems such as ƒcƒs-mutual-exclusion, construction of a multi-reader-multi-writer atomic register, probabilistic consensus,… were developed. Unfortunately, the only known implementation of a concurrent time stamp system has been theoretically unsatisfying, since it requires unbounded size time-stamps, in other words, unbounded memory. Not knowing if bounded concurrent-time-stamp-systems are at all constructible, researchers were led to constructing complicated problem-specific solutions to replace the simple unbounded ones. In this work, for the first time, a bounded implementation of a concurrent-time-stamp-system is presented. It provides a modular unbounded-to-bounded transformation of the simple unbounded solutions to problems such as above. It allows solutions to two formerly open problems, the bounded-probabilistic-consensus problem of Abrahamson [A88] and the ƒiƒo-@@@@-exclusion problem of [FLBB85], and a more efficient construction of mrmw atomic registers.

REFERENCES

• ADMS88: Y, Afek, D. Dolev, M. Merrltt, and N. Shavit, "A Bounded fifo solution to the /-exclusion problem,'* in preparation.
• A88: Karl Abrahamson, On achieving consensus using a shared memory, Proceedings of the seventh annual ACM Symposium on Principles of distributed computing, p.291-302, August 15-17, 1988, Toronto, Ontario, Canada [doi>10.1145/62546.62594]
• AG88: James H. Anderson , Mohamed G. Gouda, The Virtue of Patience: Concurrent Programming with and Without Waiting, University of Texas at Austin, Austin, TX, 1990
• ADS89: H. Attiya, D. Dolev, and N. Shavit, "A Bounded Probabilistic Shared-Memory Consensus Algorithm," unpublished manuscript.
• B88: Shai Ben-David, The global time assumption and semantics for concurrent systems, Proceedings of the seventh annual ACM Symposium on Principles of distributed computing, p.223-231, August 15-17, 1988, Toronto, Ontario, Canada [doi>10.1145/62546.62583]
• Bl87: Bard Bloom, Constructing two-writer atomic registers, Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, p.249-259, August 10-12, 1987, Vancouver, British Columbia, Canada [doi>10.1145/41840.41861]
• BP87: James E. Burns , Gary L. Peterson, Constructing multi-reader atomic values from non-atomic values, Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, p.222-231, August 10-12, 1987, Vancouver, British Columbia, Canada [doi>10.1145/41840.41859]
• CIL87: Benny Chor , Amos Israeli , Ming Li, On processor coordination using asynchronous hardware, Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, p.86-97, August 10-12, 1987, Vancouver, British Columbia, Canada [doi>10.1145/41840.41848]
• D65: E. W. Dijkstra, Solution of a problem in concurrent programming control, Communications of the ACM, v.8 n.9, p.569, Sept. 1965 [doi>10.1145/365559.365617]
• DGS88: Danny Dolev , Eli Gafni , Nir Shavit, Toward a non-atomic era: l-exclusion as a test case, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.78-92, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62220]
• FLBB79: M. $. Fischer, N. A. Lynch, J. E. Burns, and A. Borodin, "Resource Allocation with Immunity to Limited Process Failure," Proc. 20th IEEE Syrup. on Foundations of Computer Science, 1979, pp. 234-254.
• FLBB85: M.J. Fischer, N. A. Lynch, J. E. Burns, and A. Borodin, "Distributed fifo Allocation of Identical Resources Using Small Shared Space," MIT/LCS/TM-290, 1985.
• H88: Maurice P. Herlihy, Impossibility and universality results for wait-free synchronization, Proceedings of the seventh annual ACM Symposium on Principles of distributed computing, p.276-290, August 15-17, 1988, Toronto, Ontario, Canada [doi>10.1145/62546.62593]
• IL87: A. Israeli and M. Li, "Bounded Time Stamps," Proc. 28th Annual IEEE Syrup. on Foundations of Computer Science, 1987, pp. 371-382.
• K78: Howard P. Katseff, A new solution to the critical section problem, Proceedings of the tenth annual ACM symposium on Theory of computing, p.86-88, May 01-03, 1978, San Diego, California, United States [doi>10.1145/800133.804335]
• L74: Leslie Lamport, A new solution of Dijkstra's concurrent programming problem, Communications of the ACM, v.17 n.8, p.453-455, Aug. 1974 [doi>10.1145/361082.361093]
• L86a: L. Lamport, "On Interprocess Communication. Part I: Basic Formalism," Distributed Computing i, ~ 1986, 77-85.
• L86b: L. Lamport, "On Interprocess Communication. Part II: Algorithms," Distributed Computing 1, 2 1986, pp. 86-101.
• L86c: Leslie Lamport, The mutual exclusion problem: part I—a theory of interprocess communication, Journal of the ACM (JACM), v.33 n.2, p.313-326, April 1986 [doi>10.1145/5383.5384]
• L86d: Leslie Lamport, The mutual exclusion problem: partII—statement and solutions, Journal of the ACM (JACM), v.33 n.2, p.327-348, April 1986 [doi>10.1145/5383.5385]
• LV88: M. Li, and P. Vitanyi, "Uniform Construction for Wait-Free Variables," unpublished manuscript, 1988.
• LH88: E.A. Lycldama and V. Hadzilacos, "A Fair Mutual Exclusion Algorithm With Small Cornmunication Variables," submitted for publication, 1988.
• N87: Richard Newman-Wolfe, A protocol for wait-free, atomic, multi-reader shared variables, Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, p.232-248, August 10-12, 1987, Vancouver, British Columbia, Canada [doi>10.1145/41840.41860]
• P81: (3. L. Peterson, "Myths about the Mutual- Exclusion Problem," IPL 1~, 3 1981, pp. 115~ 116.
• P83: Gary L. Peterson, Concurrent Reading While Writing, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.1, p.46-55, Jan. 1983 [doi>10.1145/357195.357198]
• PB87: G.L. Peterson, and J. E. Bums, "Concurrent Reading While Writing Ii: The Multi- Writer Case," Proc. ~Sth Ann~el iEEE Syrup. on Foundations of Computer Science, 1987, pp. 383-392.
• P88: (3. L. Peterson, personal communication.
• R86: M. Raynal , D. Beeson, Algorithms for mutual exclusion, MIT Press, Cambridge, MA, 1986
• S88: R. Schaffer, "On the Correctness of Atomic Multi-Writer Registers," MIT/LCS/TM-364, June 1988.
• SAG87: Ambuj K. Singh , James H. Anderson , Mohamed G. Gouda, The elusive atomic register revisited, Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, p.206-221, August 10-12, 1987, Vancouver, British Columbia, Canada [doi>10.1145/41840.41858]
• VA86: P. Vitanyi, and B. Awerbuch, "Atomic Shared Register Access by Asynchronous Hardware," Proc. 27th Annual IEEE Syrup. on Foundations of Computer Science, 1986, pp. 233-243.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

  G. Mathematics of Computing

General Terms:
Algorithms, Design, Theory