Danny Dolev
Nir Shavit
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.
- B87.B. Bloom, "Constructing two-writer atomic registers," Proc. 6th A CAt Syrup. on Principles of Distributed Computation, 1987, pp. 249-259. Google Scholar
Digital Library
- BP87.J. E. Burns, and G. L. Peterson, "Constructing two-writer atomic registers," Proc. 6th A CM Syrup. on P l'inciplcs of Distributcd Computation, 1(".)8~, pp. 222-231 Google ScholarDigital Library
- CIL87.B. Chor, A. Israeli, ~nd M. Li, "On Processor Coordination Using Asynchronous Hardware", Proc. 6th A CM Syrup. on Principles of Distributed Computation, 1987, pp. 86-97. Google ScholarDigital Library
- CL85.K. M. Cl~andy, and L. Lamport, "Distributed Snapshot' Determining Global States of Distributed Systems," ACM Trans. on Prog. Lang. al~d Sys. i, 6 1985, pp. 63- 75. Google ScholarDigital Library
- CM84.K. M. ClJandy, and J. /vlisra, "The l)rinking Pltilosophers Problem," ACM ?Yans. on Prog. Lang. and Sys. 6, d 1984, pp. 632-646. Google ScholarDigital Library
- DDS87.D. Dolev, C. Dwork, and L. Stockmeyer, "On the MinimM Synchronism Heeded for Distributed Consensus, 3d, 1987, pp. 77-97. Google ScholarDigital Library
- 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.Google Scholar
- 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.Google Scholar
- FLP85.M. J. Fischer, N. A. l,ync!l, a. tld M. S. Paterson, "Impossibility of Distributed Consensus with One Faulty Processor," J. A CM 32, 1985, pp. 374-382. Google ScholarDigital Library
- H87.M. P. Herlihy, "W~itFree Implementations of Concurrent Objects," Technical Report, Dept. of CS, CMU, 1987.Google Scholar
- IL87.A. Israeli, and M. Li, "Bounded Time- Stamps," Proceedings of the 28th Annual Symposium on Foundations of Computer Science, 1987, pp. 371-382.Google ScholarDigital Library
- L86a.L. Lamport, "On lnterprocess Communication. Part t' Basic Formalism," Distributcd (?o'mputin9 I, 2 1986, 77-85.Google Scholar
- L86b.L. Lamport, "On Interprocess Communication. Part II: Algorithms," Distributed Computing I, 2 1986, pp. 86-101.Google ScholarCross Ref
- L86c.L. Lamport, "The Mutual Exclusion Problem. Part I: A Theory of Interprocess Communication," J. A CM 33, 2 1986, pp. 313-326. Google ScholarDigital Library
- L86d.L. Lamport, "The Mutual Exclusion Problem. Part II: Statement and Solutions,'' J. A CM 33, 2 1986, pp. 327-348. Google ScholarDigital Library
- 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.Google Scholar
- N87.R. Newman-Wolfe, "A Protocol for Waitfree Atomic, Multi Reader Shared Variables,'' Proc. 6th A CM Syrup. on Principles of Distributed Computation, 1987, pp. 232-248. Google ScholarDigital Library
- P83.G. L. Peterson, "Concurrent Reading While Writing," A CM TOPLAS 5, I 1983, pp. 46-55. Google ScholarDigital Library
- 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.Google Scholar
- 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.Google ScholarDigital Library
Index Terms
- Toward a non-atomic era: l-exclusion as a test case
Recommendations
Inferring locks for atomic sections
PLDI '08: Proceedings of the 29th ACM SIGPLAN Conference on Programming Language Design and ImplementationAtomic sections are a recent and popular idiom to support the development of concurrent programs. Updates performed within an atomic section should not be visible to other threads until the atomic section has been executed entirely. Traditionally, ...
Inferring locks for atomic sections
PLDI '08Atomic sections are a recent and popular idiom to support the development of concurrent programs. Updates performed within an atomic section should not be visible to other threads until the atomic section has been executed entirely. Traditionally, ...
Fast mutual exclusion for uniprocessors
In this paper we describe restartable atomic sequences, an optimistic mechanism for implementing simple atomic operations (such as Test-And-Set) on a uniprocessor. A thread that is suspended within a restartable atomic sequence is resumed by the ...
Comments