Yehuda Afek
Hagit Attiya
Nir Shavit
Abstract
This paper introduces a general formulation of atomic snapshot memory, a shared memory partitioned into words written (updated) by individual processes, or instantaneously read (scanned) in its entirety. This paper presents three wait-free implementations of atomic snapshot memory. The first implementation in this paper uses unbounded (integer) fields in these registers, and is particularly easy to understand. The second implementation uses bounded registers. Its correctness proof follows the ideas of the unbounded implementation. Both constructions implement a single-writer snapshot memory, in which each word may be updated by only one process, from single-writer, n-reader registers. The third algorithm implements a multi-writer snapshot memory from atomic n-writer, n-reader registers, again echoing key ideas from the earlier constructions. All operations require Θ(n2) reads and writes to the component shared registers in the worst case. —Authors' Abstract
- 1 ~ABRAHAMSON, K. On achieving consensus using a shared memory. In Procce&tzgs of the 7th ~Antzual ACM Symposium on Prmctples of Dz~trtb~ted Computblg (Toronto, Ont., Canada, Aug. ~15-17). ACM, New York, 1988, pp. 291-302. Google Scholar
- 2 ~ANDERSON, J.H. Composite registers. Tech. Rep. TR-89-25. Dept. Comput. Sci., Univ. Texas ~at Austin, Austin, Tex., Sept. 1989. Google Scholar
- 3 ~ANDERSON, J.H. Multiple-writer composite registers. Tech. Rep. TR-89-26. Dept. Comput. ~Sci., Univ. Texas at Austin, Austin, Tex., Sept. 1989. Google Scholar
- 4 ~ANDERSON, J. H. Composite registers. In Proceedings of the 9th Annual ACM Symposium ~on Principles of Distributed Computing (Quebec City, Que., Canada, Aug. 22-24). ACM, ~New York, 1990, pp. 15 29. Google Scholar
- 5 ~ANDERSON, J. H., AND GOUDA, M.G. The virtue of patience: Concurrent programming with ~and without waiting. Tech. Rep. TR.90.23. Dept. Comput. Sci., Univ. Texas at Austin, Austin, ~Tex., July 1990. Google Scholar
- 6 ~ASPNES, J. Time- and space-efficient randomized consensus. In Proceedings of the 9th Annual ~ACM Symposium on Principles of Distributed Computing (Quebec City, Que., Canada, Aug. ~22-24). ACM, New York, 1990, pp. 325-331. Google Scholar
- 7 ~ASPNES, J., AND HERLIHY, U. P. Fast randomized consensus using shared memory. ~J. Algorithms (Sept. 1990), pp. 441-461. Google Scholar
- 8 ~ASPNES, J., AND HERLtHY, M.P. Wait-free data structures in the asychronous PRAM model. ~In Proceedings of the 2nd Annual Symposimn on Parallel Algorithms and Architectures (July). ~ACM, New York, 1990, pp. 340-349. Google Scholar
- 9 ~ATnYA, H., BAR-NoY, A., AND DOLEV, D, Sharing memory rebustly in message-passing ~systems. In Proceedings of the 9th Annual ACM Symposium on Principles of Distributed ~Computing (Quebec City, Que., Canada, Aug. 22-24). ACM, New York, 1990, pp. 363-375. Google Scholar
- 10 ~AqTIYA, H., DOLEV, D., AND SHAVIT, N. Bounded polynomial randomized consensus. In ~Proceedings o)' the 8th Annual ACM Symposmm on Principles of Distributed Computing (Edmon- ~ton, Alb., Canada, Aug. 14-16). ACM New York, 1989, pp. 281 293. Google Scholar
- 11 ~ATTIYA, H., LYNCH, N. A., AND SHAVIT, N. Are wait-free algorithms fast? In Proceedings of ~the 31st IEEE Symposzum on Foundations of Computer Science (Oct.). IEEE New York, 1990, ~pp. 55-64.Google Scholar
- 12 ~BRACHA, G., AND TOUEG, S. Distributed deadlock detection. Dist,: Computing 2 (1987), ~127-138.Google Scholar
- 13 ~CHAND~, K. M., AND LAMPORT, L. Distributed snapsots: Determining global states of ~distributed systems. ACM Trans. Cornpttt, Syst. 3, I (Jan. 1985) 63 75. Google Scholar
- 14 ~DOLEV, D., GAFNI, E., AND SHAVIT, N. Toward a non-atomic era: /-exclusion as a test case. ~In Proceedings of the 20th Annual ACM Symposium on tile TheoO' of Computing (Chicago, Ill., ~May 2-4). ACM, New York 1988, pp. 78-92. Google Scholar
- 15 ~DOLEV, D., AND SHAV1T, N. Bounded concurrent time-stamp systems are constructible! In ~Proceedblgs o} ttle 21st Anmtal ACM $?mposh~m on Theory of Computing (Seattle, Wash., May ~15-17). ACM, New York, 1989, pp. 454-465, Google Scholar
- 16 ~GAFNI, E. Perspective on distributed network protocols: A case for building blocks. In ~Proceedings of MILCOM-86 (Monterey, Calif., Oct.). IEEE, New York, 1986, pp. 1.1.1-1.1.5.Google Scholar
- 17 ~HERLIHY, M.P. Wait-free synchronization, ACM Trans. Prog. Lang. Syst. 13, 1 (Jan. 1991), ~124-149. Google Scholar
- 18 ~HERLIHY, M. P., AND WING, J. M. Linearizability: A correctness condition for concurrent ~objects. ACM Trans. Prog. Lang. Syst. 12, 3 (July 1990), 463 492. Google Scholar
- 19 ~KATSErF, H.P. A new solution to the critical section problem. In Proceedings of the lOth ~Annual A CM Symposium oil the Theory of Computing (San Diego, Calif., May 1-3). ACM, New ~York, 1978, pp. 86-88. Google Scholar
- 20 ~LAMPORT, L. The mutual exclusion problem. Part II: Statement and solutions. J. ACM 33, 2 ~(Feb. 1986), 327-348. Google Scholar
- 21 ~LA~lPORr', L. On interprocess communication. Part I: Basic formalism. Dist. Comput. 1, 1 ~(1986), 77-85.Google Scholar
- 22 ~LAMPORT, L. On interprocess communication. Part II: Algorithms, Dist. Comput. 1, 1 (1986), ~86-101.Google Scholar
- 23 ~Ll, M., TROMP, J., AND VITANYI, P. M.B. How to share concurrent wast-free variables. In ~ProceedblgsoJ I(MLP '89. (Stresa, Italy, July 11-15). Lecture Notes in Computer Science, vol. ~372. Springer Verlag, New York, 1990, pp. 488-505. (Expanded version: Report CS-R8916, ~CWL Amsterdam, The Netherlands, Apr, 1989).Google Scholar
- 24 ~LYNCH, N. A., AND Tu"FrLE, n. Hierarchical correctness proofs for distributed algorithms. In ~Proceedb~gs of 6th Annual ACM $~wnpositm~ on Principles of Distribttted Computing (Aug.) ~ACM, New York, 1987, pp. 137-151. (Expanded version available as Tech. Rep. ~MIT/LCS/TR-387, Laboratory for Computer Science, Massachusetts Institute of Technol- ~ogy, Cambridge, Mass. {Apr. 1987)). Google Scholar
- 25 ~MISRA, J. Axioms for memory access in asynchronous hardware systems. ACM Trans. Prog. ~Lang. Svst. 8, 1 (Jan. 1986), 142 153. Google Scholar
- 26 ~OWICKi, S. Axiomatic Proof Techmques for Parallel Programs. Ph.D. dissertation. Cornell ~Univ., Aug. 1975. Google Scholar
- 27 ~OWlCK~, S., AND aRIES, D. An axiomatic proof technique for parallel programs. Act Inf 6, 1 ~(Jan. 1976), 319-340.Google Scholar
- 28 ~PETERSON, a.L. Concurrent reading whfie writing. ACM Trans. Prog. Lang. Syst. 5, 1 (Jan. ~1983), 46-55. Google Scholar
- 29 ~PETERSON, G. m., AND BURNS, J.E. Concurrent reading while writing II: The mulmwnter ~case. In Proceedings of the 28th Annual IEEE 5~mpostum on Foundations of Computer Science ~(Oct.). IEEE, New York, 1987, pp. 383-392Google Scholar
- 30 ~SCH^FFER, R. On the correctness of atomic multi-writer registers. Tech. Rep. ~M1T/LCS/TM-364. Laboratory for Computer Science, Massachusetts Institute of Technol- ~ogy, Cambridge, Mass., June 1988.Google Scholar
- 31 ~VITANYI, P. M. U., AND AWERBUCH, B. Atomic shared register access by asynchronous ~hardware. In Proceedzngs of 27th Annual Sympostum on Foundatzons oJ Computer Sczence ~(Oct.). IEEE, New York, 1986, pp. 233 243.Google Scholar
Index Terms
- Atomic snapshots of shared memory
Recommendations
Interrupting snapshots and the Java™ size() method
DISC'09: Proceedings of the 23rd international conference on Distributed computingThe Java™ developers kit requires a size() operation for all objects. Unfortunately, the best known solution, available in the Java concurrency package, has a blocking concurrent implementation that does not scale. This paper presents a highly scalable ...
Concurrent tries with efficient non-blocking snapshots
PPoPP '12: Proceedings of the 17th ACM SIGPLAN symposium on Principles and Practice of Parallel ProgrammingWe describe a non-blocking concurrent hash trie based on shared-memory single-word compare-and-swap instructions. The hash trie supports standard mutable lock-free operations such as insertion, removal, lookup and their conditional variants. To ensure ...
Concurrent tries with efficient non-blocking snapshots
PPOPP '12We describe a non-blocking concurrent hash trie based on shared-memory single-word compare-and-swap instructions. The hash trie supports standard mutable lock-free operations such as insertion, removal, lookup and their conditional variants. To ensure ...
Reviews
Edward A. Feustel
Achieving a consistent view of the state of concurrent computations is helpful in verifying the correct operation of those computations. The authors have made a contribution to theory by designing an algorithm that takes an atomic snapshot of computations. The work is supplemented by a large bibliography.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments