ACM Portal
  Subscribe (Full Service)    Register (Limited Service, Free)    Login
  Search:   The ACM Digital Library   The Guide
  
ACM Home Page
Please provide us with feedback. Feedback
Wait-free data structures in the asynchronous PRAM model
Full text PdfPdf (1.13 MB)
Source ACM Symposium on Parallel Algorithms and Architectures archive
Proceedings of the second annual ACM symposium on Parallel algorithms and architectures table of contents
Island of Crete, Greece
Pages: 340 - 349  
Year of Publication: 1990
ISBN:0-89791-370-1
Authors
J. Aspnes  School of Computer Science, Carnegie-Mellon University, Pittsburgh, PA
M. Herlihy  Digital Equipment Corporation, Cambridge Research Laboratory, One Kendall Square, Cambridge MA
Sponsors
IEEE-CS : Computer Society
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGARCH: ACM Special Interest Group on Computer Architecture
CTI : Computer Technology Inst.
EATCS : European Association for Theoretical Computer Science
Computer Tech Inst. : Computer Technology Institute
Publisher
ACM  New York, NY, USA
Bibliometrics
Downloads (6 Weeks): 5,   Downloads (12 Months): 30,   Citation Count: 37
Additional Information:

references   cited by   index terms   collaborative colleagues  

Tools and Actions: Request Permissions Request Permissions    Review this Article  
DOI Bookmark: Use this link to bookmark this Article: http://doi.acm.org/10.1145/97444.97701
What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

1
Yehuda Afek , Danny Dolev , Hagit Attiya , Eli Gafni , Michael Merritt , Nir Shavit, Atomic snapshots of shared memory, Proceedings of the ninth annual ACM symposium on Principles of distributed computing, p.1-13, August 22-24, 1990, Quebec City, Quebec, Canada  [doi>10.1145/93385.93394]
 
2
James H. Anderson, Composite Registers, University of Texas at Austin, Austin, TX, 1990
 
3
J. Aspnes and M.P. Herlihy. Randomized algorithms for wait-free synchronization. Submitted for publication.
4
Philip A. Bernstein , Nathan Goodman, Concurrency Control in Distributed Database Systems, ACM Computing Surveys (CSUR), v.13 n.2, p.185-221, June 1981  [doi>10.1145/356842.356846]
5
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]
6
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]
7
R. Cole , O. Zajicek, The APRAM: incorporating asynchrony into the PRAM model, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.169-178, June 18-21, 1989, Santa Fe, New Mexico, United States  [doi>10.1145/72935.72954]
8
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]
9
P. B. Gibbons, A more practical PRAM model, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.158-168, June 18-21, 1989, Santa Fe, New Mexico, United States  [doi>10.1145/72935.72953]
10
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]
11
Maurice P. Herlihy, Impossibility and universality results for wait-free synchronization, Proceedings of the seventh annual ACM Symposium on Principles of distributed computing, p.276-290, August 15-17, 1988, Toronto, Ontario, Canada  [doi>10.1145/62546.62593]
12
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]
13
M. P. Herlihy , J. M. Wing, Axioms for concurrent objects, Proceedings of the 14th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.13-26, January 21-23, 1987, Munich, West Germany  [doi>10.1145/41625.41627]
14
Leslie Lamport, Concurrent reading and writing, Communications of the ACM, v.20 n.11, p.806-811, Nov. 1977  [doi>10.1145/359863.359878]
15
Leslie Lamport, Time, clocks, and the ordering of events in a distributed system, Communications of the ACM, v.21 n.7, p.558-565, July 1978  [doi>10.1145/359545.359563]
 
16
L. Lamport. How to make a multiprocessor computer that correctly executes multiprocess programs. IEEE Transactions on Computers, C-28(9):690, September 1979.
 
17
L. Lamport. On interprocess communication, parts i and ii. Distributed Computing, 1:77-101, 1986.
 
18
N.A. Lyltch and M.R. Turtle. An introduction to input/output automata. Technical Report MIT/LCS/TM-373, MIT Laboratory for Computer Science, November 1988.
19
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]
20
Christos H. Papadimitriou, The serializability of concurrent database updates, Journal of the ACM (JACM), v.26 n.4, p.631-653, Oct. 1979  [doi>10.1145/322154.322158]
21
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]
 
22
G.L. Pctcrson and J.E. Burns. Concurrent ~eading while writing ii: the multi-writer case. Technical Report GIT-ICS-86/26, Georgia Institute of Technology, December 1986.
23
Ambuj K. Singh , James H. Anderson , Mohamed G. Gouda, The elusive atomic register revisited, Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, p.206-221, August 10-12, 1987, Vancouver, British Columbia, Canada  [doi>10.1145/41840.41858]
 
24
P. Vitanyi and B. Awerbuch. Atomic shared register access by asynchronous hardware. In Proceedings of of the ~Tth IEEE Symposium on Foundations of Computer Science, pages 223-243, 1986. See also errata in SIGACT News 18(4), Summer, 1987.
 
25
W. E. Weihl, SPECIFICATION AND IMPLEMENTATION OF ATOMIC DATA TYPES, Massachusetts Institute of Technology, Cambridge, MA, 1984

CITED BY  37
Phillip B. Gibbons , Michael Merritt, Specifying non-blocking shared memories (extended abstract), Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures, p.306-315, June 29-July 01, 1992, San Diego, California, United States
James Aspnes , Orli Waarts, Modular competitiveness for distributed algorithms, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.237-246, May 22-24, 1996, Philadelphia, Pennsylvania, United States
Yehuda Afek , Danny Dolev , Hagit Attiya , Eli Gafni , Michael Merritt , Nir Shavit, Atomic snapshots of shared memory, Proceedings of the ninth annual ACM symposium on Principles of distributed computing, p.1-13, August 22-24, 1990, Quebec City, Quebec, Canada
Hagit Attiya , Ophir Rachman, Atomic snapshots in O(n log n) operations, Proceedings of the twelfth annual ACM symposium on Principles of distributed computing, p.29-40, August 15-18, 1993, Ithaca, New York, United States
Richard J. Anderson, Primitives for asynchronous list compression, Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures, p.199-208, June 29-July 01, 1992, San Diego, California, United States
Eric Ruppert, Determining consensus numbers, Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing, p.93-99, August 21-24, 1997, Santa Barbara, California, United States
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
Hagit Attiya , Amotz Bar-Noy , Danny Dolev, Sharing memory robustly in message-passing systems, Journal of the ACM (JACM), v.42 n.1, p.124-142, Jan. 1995
Richard J. Anderson , Heather Woll, Wait-free parallel algorithms for the union-find problem, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.370-380, May 05-08, 1991, New Orleans, Louisiana, United States
Shlomo Moran , Gadi Taubenfeld , Irit Yadin, Concurrent counting, Proceedings of the eleventh annual ACM symposium on Principles of distributed computing, p.59-70, August 10-12, 1992, Vancouver, British Columbia, Canada
James Aspnes , William Hurwood, Spreading rumors rapidly despite an adversary, Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing, p.143-151, May 23-26, 1996, Philadelphia, Pennsylvania, United States
L. M. Kirousis , P. Spirakis , P. Tsigas, Reading Many Variables in One Atomic Operation: Solutions with Linear or Sublinear Complexity, IEEE Transactions on Parallel and Distributed Systems, v.5 n.7, p.688-696, July 1994
Panagiota Fatourou , Faith Fich , Eric Ruppert, A tight time lower bound for space-optimal implementations of multi-writer snapshots, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
Jaap-Henk Hoepman , Marina Papatriantafilou , Philippas Tsigas, Self-stabilization of wait-free shared memory objects, Journal of Parallel and Distributed Computing, v.62 n.5, p.818-842, May 2002
Bogdan S. Chlebus , Dariusz R. Kowalski , Alexander A. Shvartsman, Collective asynchronous reading with polylogarithmic worst-case overhead, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA
Bogdan S. Chlebus , Leszek Gasieniec , Andrzej Pelc, Deterministic computations on a PRAM with static processor and memory faults, Fundamenta Informaticae, v.55 n.3-4, p.285-306, June 2003
Faith Fich , Eric Ruppert, Hundreds of impossibility results for distributed computing, Distributed Computing, v.16 n.2-3, p.121-163, September 2003
Yehuda Afek , Hagit Attiya , Danny Dolev , Eli Gafni , Michael Merritt , Nir Shavit, Atomic snapshots of shared memory, Journal of the ACM (JACM), v.40 n.4, p.873-890, Sept. 1993
Maurice Herlihy, Randomized wait-free concurrent objects (extended abstract), Proceedings of the tenth annual ACM symposium on Principles of distributed computing, p.11-21, August 19-21, 1991, Montreal, Quebec, Canada
Cynthia Dwork , Maurice Herlihy, Bounded round number, Proceedings of the twelfth annual ACM symposium on Principles of distributed computing, p.53-64, August 15-18, 1993, Ithaca, New York, United States
Panagiota Fatourou , Faith Fich , Eric Ruppert, Space-optimal multi-writer snapshot objects are slow, Proceedings of the twenty-first annual symposium on Principles of distributed computing, July 21-24, 2002, Monterey, California
James Aspnes , Orli Waarts, Compositional competitiveness for distributed algorithms, Journal of Algorithms, v.54 n.2, p.127-151, February 2005
Alex Brodsky , Faith Ellen Fich, Efficient synchronous snapshots, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada
Håkan Sundell , Philippas Tsigas, Scalable and lock-free concurrent dictionaries, Proceedings of the 2004 ACM symposium on Applied computing, March 14-17, 2004, Nicosia, Cyprus
James H. Anderson, Composite registers, Distributed Computing, v.6 n.3, p.141-154, April 1993
Hagit Attiya , Maurice Herlihy , Ophir Rachman, Atomic snapshots using lattice agreement, Distributed Computing, v.8 n.3, p.121-132, March 1995
Bogdan S. Chlebus , Dariusz R. Kowalski, Cooperative asynchronous update of shared memory, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
Prasad Jayanti, An optimal multi-writer snapshot algorithm, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
Grzegorz Malewicz, A tight analysis and near-optimal instances of the algorithm of Anderson and Woll, Theoretical Computer Science, v.329 n.1-3, p.285-301, 13 December 2004
James H. Anderson, Multi-writer composite registers, Distributed Computing, v.7 n.4, p.175-195, May 1994
Guojing Cong , David A. Bader, Designing irregular parallel algorithms with mutual exclusion and lock-free protocols, Journal of Parallel and Distributed Computing, v.66 n.6, p.854-866, June 2006
Panagiota Fatourou , Faith Ellen Fich , Eric Ruppert, Time-space tradeoffs for implementations of snapshots, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA
Panagiota Fatourou , Nikolaos D. Kallimanis, Single-scanner multi-writer snapshot implementations are fast!, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, July 23-26, 2006, Denver, Colorado, USA
Michael T. Goodrich, Parallel algorithms column 1: models of computation, ACM SIGACT News, v.24 n.4, p.16-21, Dec. 1993
Hagit Attiya , Rachid Guerraoui , Eric Ruppert, Partial snapshot objects, Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures, June 14-16, 2008, Munich, Germany
Panagiota Fatourou , Nikolaos D. Kallimanis, Time-optimal, space-efficient single-scanner snapshots & multi-scanner snapshots using CAS, Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, August 12-15, 2007, Portland, Oregon, USA
Faith Ellen , Panagiota Fatourou , Eric Ruppert, Time lower bounds for implementations of multi-writer snapshots, Journal of the ACM (JACM), v.54 n.6, p.30-es, December 2007

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Unbounded-action devices (e.g., cellular automata, circuits, networks of machines)
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS


General Terms:
Algorithms, Verification

Collaborative Colleagues:
J. Aspnes: colleagues
M. Herlihy: colleagues

The ACM Portal is published by the Association for Computing Machinery. Copyright © 2009 ACM, Inc.
Terms of Usage   Privacy Policy   Code of Ethics   Contact Us

Useful downloads: Adobe Acrobat    QuickTime    Windows Media Player    Real Player