Shlomo Moran
ABSTRACT
Our purpose is to implement clocks and, in general, counters in a shared memory environment. A concurrent counter is a counter that can be incremented and read, possibly at the same time by many processes. We study counters that achieve high level of concurrency and thus are likely to reduce memory contention; require only weak atomicity and thus are easy to implement; do not depend on the initial state of the memory and hence are more robust to memory changes; and are wait-free - one process cannot prevent another process from finishing its increment or read operations - and thus can tolerate any number of process failures. We concentrate on providing upper and lower bounds on the space complexity of the counters studied.
- AG91.J.H. Anderson and B. Gro~elj. Beyond atomic registers: Bounded waitfree implementations of nontrivial objects. In Fifth International Workshop on Distributed Algorithms, October 1991. Submitted for publication. Google Scholar
Digital Library
- AH90.J. Aspnes and M. Herlihy. Fast randomized consensus using shared memory. Journal of Algorithms, 11(3):441- 460, September 1990. Google ScholarDigital Library
- AH90.J. Aspnes and M. Herlihy. Wait-free data structures in the asynchronous PRAM model. In Proceedings of the second Annual A CM symposium on parallel architectures and algorithms, pages 340-349, July 1990. Google ScholarDigital Library
- AHS91.J. Aspnes, M. Herlihy, and N. Shavit. Counting networks and multi-processor coordination. In Proc. 23rd A CM Syrup. on Theory of Computing, pages 348-358, May 1991. Google ScholarDigital Library
- Dij74.E.W. Dijkstra. Self-stablizing systems in spite of distributed control. Communications of the A CM, 17:643-644, 1974. Google ScholarDigital Library
- Fis83.M.J. Fischer. The consensus problem in unreliable distributed systems (a brief survey). In M. Karpinsky, editor, Foundations of Computation Theory, pages 127-140. Lecture Notes in Computer Science, vol. 158, Springer- Verlag, 1983. Google ScholarDigital Library
- FMT91.M.J. Fischer, S. Moran, and G. Taubenfeld. Space-efficient asynchronous consensus without shared memory initialization. Technion Report #707, Computer Science Department, The Technion, August 1990. Submitted for publication, 1991.Google Scholar
- FMRT90.M.J. Fischer, S. Moran, S. Rudich, and G. Taubenfeld. The wakeup problem. In Proc. ~~st A CM Symp. on Theory of Computing, pages 106-116, May 1990. See also Technion Report #644, Computer Science Department, The Technion, August 1990. Google ScholarDigital Library
- Gar72.M. Gardner. Mathematical games: The curious properties of the Gray code and how it can be used to solve puzzles. Scientific American, pages 106-109, August 1972.Google Scholar
- Gil58.E.N. Gilbert. Gray codes and paths on the n-cube. The bell system technical journal, 37(9):815-826, May 1958.Google Scholar
- Gra53.F. Gray. Pulse code communication. U. S. Patent 2 632 058, March 1953.Google Scholar
- Koh70.Z. Kohavi. Switching and Finite A utomata Theory. McGrow-Hill Publication, 1970. Google ScholarDigital Library
- KMZ84.E. Korach, S. Moran and S. Zaks, Tight lower and upper bounds for some distributed algorithms for complete network of processors. In Proc. 3th A CM Symp. on Principle of distributed Computing, pages 199-207, August 1984. Google ScholarDigital Library
- Lam86.L. Lamport. On interprocess communication, parts i and II. Distributed Computing, 1 (2):77-101, 1986.Google ScholarCross Ref
- Lam77.L. Lamport. Concurrent reading and writing. Communications of the A CM, 20:806-811, 1977. Google ScholarDigital Library
- Lam90.L. Lamport. Concurrent reading and writing of clocks. A CM Trans. on Computer Systems, 8(4):305-310, 1990. Google ScholarDigital Library
- Pet82.G.L. Peterson. An O(nlogn) unidirectional algorithm for the circular extrema problem. A CM Trans. on Programrai~g Language~ and System~, 4(4):758-762, 1982. Google ScholarDigital Library
Index Terms
- Concurrent counting
Recommendations
Concurrent Counting
In this paper we study implementations of concurrent counters, which count modulo some (large) integerm, using only small valued objects. A concurrent counter is a counter that can be incremented and read, possibly at the same time, by many processes. ...
Looking for efficient implementations of concurrent objects
PaCT'11: Proceedings of the 11th international conference on Parallel computing technologiesAs introduced by Taubenfeld, a contention-sensitive implementation of a concurrent object is an implementation such that the overhead introduced by locking is eliminated in the common cases, i.e., when there is no contention or when the operations ...
Transactions for concurrent object-oriented programming systems
OOPSLA/ECOOP '88: Proceedings of the 1988 ACM SIGPLAN workshop on Object-based concurrent programmingConcurrent object-oriented programming systems (COOPS) require support for fault tolerance, concurrency control, consistent commitment of changes and program-initiated rollback. It is sometimes suggested that the classical transaction processing model ...
Comments