Atomic snapshots of shared memory

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 &THgr;(n2) reads and writes to the component shared registers in the worst case. —Authors' Abstract

REFERENCES

• 1: 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]
• 2: James H. Anderson, Composite Registers, University of Texas at Austin, Austin, TX, 1990
• 3: James H. Anderson, Multiple-Writer Composite Registers, University of Texas at Austin, Austin, TX, 1990
• 4: James Anderson, Composite registers, Proceedings of the ninth annual ACM symposium on Principles of distributed computing, p.15-29, August 22-24, 1990, Quebec City, Quebec, Canada [doi>10.1145/93385.93396]
• 5: James H. Anderson , Mohamed G. Gouda, The Virtue of Patience: Concurrent Programming with and Without Waiting, University of Texas at Austin, Austin, TX, 1990
• 6: James Aspnes, Time-and space-efficient randomized consensus, Proceedings of the ninth annual ACM symposium on Principles of distributed computing, p.325-331, August 22-24, 1990, Quebec City, Quebec, Canada [doi>10.1145/93385.93433]
• 7: James Aspnes , M. Herlihy, Fast randomized consensus using shared memory, Journal of Algorithms, v.11 n.3, p.441-461, Sep. 1990 [doi>10.1016/0196-6774(90)90021-6]
• 8: J. Aspnes , M. Herlihy, Wait-free data structures in the asynchronous PRAM model, Proceedings of the second annual ACM symposium on Parallel algorithms and architectures, p.340-349, July 02-06, 1990, Island of Crete, Greece [doi>10.1145/97444.97701]
• 9: Hagit Attiya , Amotz Bar-Noy , Danny Dolev, Sharing memory robustly in message-passing systems, Proceedings of the ninth annual ACM symposium on Principles of distributed computing, p.363-375, August 22-24, 1990, Quebec City, Quebec, Canada [doi>10.1145/93385.93441]
• 10: H. Attiya , D. Dolev , N. Shavit, Bounded polynomial randomized consensus, Proceedings of the eighth annual ACM Symposium on Principles of distributed computing, p.281-293, June 1989, Edmonton, Alberta, Canada [doi>10.1145/72981.73001]
• 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.
• 12: ~BRACHA, G., AND TOUEG, S. Distributed deadlock detection. Dist,: Computing 2 (1987), ~127-138.
• 13: 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]
• 14: 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]
• 15: D. Dolev , N. Shavit, Bounded concurrrent time-stamp systems are constructible, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.454-466, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73051]
• 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.
• 17: Maurice Herlihy, Wait-free synchronization, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.1, p.124-149, Jan. 1991 [doi>10.1145/114005.102808]
• 18: Maurice P. Herlihy , Jeannette M. Wing, Linearizability: a correctness condition for concurrent objects, ACM Transactions on Programming Languages and Systems (TOPLAS), v.12 n.3, p.463-492, July 1990 [doi>10.1145/78969.78972]
• 19: 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]
• 20: 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]
• 21: ~LA~lPORr', L. On interprocess communication. Part I: Basic formalism. Dist. Comput. 1, 1 ~(1986), 77-85.
• 22: ~LAMPORT, L. On interprocess communication. Part II: Algorithms, Dist. Comput. 1, 1 (1986), ~86-101.
• 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).
• 24: Nancy A. Lynch , Mark R. Tuttle, Hierarchical correctness proofs for distributed algorithms, Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, p.137-151, August 10-12, 1987, Vancouver, British Columbia, Canada [doi>10.1145/41840.41852]
• 25: J. Misra, Axioms for memory access in asynchronous hardware systems, ACM Transactions on Programming Languages and Systems (TOPLAS), v.8 n.1, p.142-153, Jan. 1986 [doi>10.1145/5001.5007]
• 26: Susan Speer Owicki, Axiomatic proof techniques for parallel programs., 1975
• 27: ~OWlCK~, S., AND aRIES, D. An axiomatic proof technique for parallel programs. Act Inf 6, 1 ~(Jan. 1976), 319-340.
• 28: 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]
• 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-392
• 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.
• 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.

INDEX TERMS

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

Additional Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.2 Design Styles
          Subjects: Shared memory

  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Multiple-instruction-stream, multiple-data-stream processors (MIMD)

General Terms:
Algorithms, Design, Theory

Keywords:
atomic, consistent state, fault-tolerance, snapshot