Toward a non-atomic era: l-exclusion as a test case

ABSTRACT

Most of the research in concurrency control has been based on the existence of strong synchronization primitives such as test and set. Following Lamport, recent research promoting the use of weaker primitives, “safe” rather than “atomic,” has resulted in construction of atomic registers from safe ones, in the belief that they would be useful tools for process synchronization. We argue that the properties provided by atomic operations may be too powerful, masking core difficulties of problems and leading to inefficiency. We therefore advocate a different approach, to skip the intermediate step of achieving atomicity, and solve problems directly from safe registers. Though it has been shown that “test and set” cannot be implemented from safe registers, we show how to achieve a fair solution to l-exclusion, a classical concurrency control problem previously solved assuming a very powerful form of atomic “test and set”. We do so using safe registers alone and without introducing atomicity. The solution is based on the construction of a simple novel non-atomic synchronization primitive.

REFERENCES

• B87: 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]
• CL85: K. Mani Chandy , Leslie Lamport, Distributed snapshots: determining global states of distributed systems, ACM Transactions on Computer Systems (TOCS), v.3 n.1, p.63-75, Feb. 1985 [doi>10.1145/214451.214456]
• CM84: K. M. Chandy , J. Misra, The drinking philosophers problem, ACM Transactions on Programming Languages and Systems (TOPLAS), v.6 n.4, p.632-646, Oct. 1984 [doi>10.1145/1780.1804]
• DDS87: Danny Dolev , Cynthia Dwork , Larry Stockmeyer, On the minimal synchronism needed for distributed consensus, Journal of the ACM (JACM), v.34 n.1, p.77-97, Jan. 1987 [doi>10.1145/7531.7533]
• FLBB79: M. J. Fischer, N. A. Lynch, J. E. Burns, and A. Borodin, "Resource Allocatio~ with Immunity to I,imitcd Process Failure,'' Proc. 20th IEEE Syrup. on Foundatio~.$ of Computer ,%ic~wc, 1979, pp. 234- 25.t.
• 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.
• FLP85: Michael J. Fischer , Nancy A. Lynch , Michael S. Paterson, Impossibility of distributed consensus with one faulty process, Journal of the ACM (JACM), v.32 n.2, p.374-382, April 1985 [doi>10.1145/3149.214121]
• H87: M. P. Herlihy, "W~itFree Implementations of Concurrent Objects," Technical Report, Dept. of CS, CMU, 1987.
• IL87: A. Israeli, and M. Li, "Bounded Time- Stamps," Proceedings of the 28th Annual Symposium on Foundations of Computer Science, 1987, pp. 371-382.
• L86a: L. Lamport, "On lnterprocess Communication. Part t' Basic Formalism," Distributcd (?o'mputin9 I, 2 1986, 77-85.
• L86b: L. Lamport, "On Interprocess Communication. Part II: Algorithms," Distributed Computing I, 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]
• LA87: M. G. Loui, and H. Abu-Amara, "Memory Requirements for Agreement Among l, lnrelia,l~le Asynchronous Processes", Ad- ~,a~ccs in Computi~l,g Research, vol. ,1, 1987, pp. 163-183.
• 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]
• 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. !'cterson, and J. E.Burns, "concurrent Reading While Writing," Proceedings of the ~8th Annual Symposium on lCbundations of Computer Science, 1987, pp. 383-392.
• VA86: P. Vitanyi, and B. Awerbuch, Atomic shared register access by asynchronous hardware, Proceedings of the 27th Annual Symposium on Foundations of Computer Science, 1986, pp. 233-243.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Synchronization

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Multiprocessing/multiprogramming/multitasking; Concurrency

General Terms:
Algorithms, Design, Performance, Theory