skip to main content
10.1145/103418.103459acmconferencesArticle/Chapter ViewAbstractPublication PagesstocConference Proceedingsconference-collections
Article
Free Access

Combining tentative and definite executions for very fast dependable parallel computing

Authors Info & Claims
Published:03 January 1991Publication History
First page image

References

  1. ACS87.A. Aggarwal, A. Chandra, and M. Snir, "Hierarchical Memory with Block transfer," Proc. #Sth IEEE Syrup. on Foundation8 of Computer Science, pp. 204--216, 1987.Google ScholarGoogle Scholar
  2. AHU74.A. Aho, 3. ttopcroft, and 3. Ullman, "The Design and Analysis of Computer Algorithma," Addison-Wesley, 1974. Google ScholarGoogle ScholarDigital LibraryDigital Library
  3. BHG87.P. Bernstein, V. Had#ilacos, and N. Goodman, Concurrency Control and Recorery in Database Systems, Addison-Wesley, 1987. Google ScholarGoogle ScholarDigital LibraryDigital Library
  4. Br74.R. Brent, "The Parallel Evaluation of General Arithmetic Expressions," JACM, vo}. 21, no. 3, pp. 201-206, 1974. Google ScholarGoogle ScholarDigital LibraryDigital Library
  5. CDR86.S. Cook, C. Dwork, and 1%. Reischuk, "Upper and Lower time Bounds for P#rallel Rsndom Access Machines without Simultaneous Writes," SIAM J. Comp#ing, vol. 15, no. 1, pp. 87-97, 1986. Google ScholarGoogle ScholarDigital LibraryDigital Library
  6. CGM88.W. Cellary, E. Gelenbe, and T. Morzy, Concurrency Control in Distributed Database Systems, North-Holland, 1988. Google ScholarGoogle ScholarDigital LibraryDigital Library
  7. CZ89.R. Cole and O. Zajicek, "The APRAM: Incorporating Asynchrony into the PRAM Model," Proc. 1989 A CM Syrup. on Parallel Algorithms and Architec#ul'es, pp. 170-178, 1989. Google ScholarGoogle ScholarDigital LibraryDigital Library
  8. CZ90.It. Cole and O. Zsjicek, "The Expected Advantage of Asynchrony," Proc. #nd Annual A CM Syrup. on Parallel Algorithms and Architectures, pp. 85-94, 1990. Google ScholarGoogle ScholarDigital LibraryDigital Library
  9. FW78.S. Fortune and J. Wyllie, "Parallelism in Random Access Machines," Proc. l Oth ACM Syrup. on Theory of Computing, pp. 114-118, 1978. Google ScholarGoogle ScholarDigital LibraryDigital Library
  10. Gi89.P. Gibbons, "A More Practical PRAM Model," Proc. 1989 A CM Syrup. on Parallel Algorithms and Architectures, pp. 158-168, 1989. Google ScholarGoogle ScholarDigital LibraryDigital Library
  11. Je90.D. Jefferson, "Virtual Time II: Storage Management in Distributed Simulation,# Proc. #th A CM Syrup. on Principles of Distributed Computing, pp. 75-89, 1990. Google ScholarGoogle ScholarDigital LibraryDigital Library
  12. KS89.P. Kanellakis and A. Shvartsman, "Efficient Parallel Algorithms Can be Made Robust,# Tech. Rep. CS-89-35, Brown Univ., pp. 1- 28, October 24, 1989. (Preliminary version appeared in Proc, 8th A UM Syrup, on Principlea of Distributed Computing, pp. 211- 222, 1989.) Google ScholarGoogle ScholarDigital LibraryDigital Library
  13. KS90.P. Kaaellakis and A. Shvartsman, "On Efficient Parallel Algorithms in the Presence of Omission Errors,# Unpnblished manuscript, October 9, 1990.Google ScholarGoogle Scholar
  14. KPS90.Z. Kedem, K. Palem, and P. Spirakis, "Efficient Robust Parallel Computations," Proc. #nd A CM Symp. on Theory of Computing, pp. 138-148, 1990. Google ScholarGoogle ScholarDigital LibraryDigital Library
  15. MPS89.C. Martel, A. Park, and R. Subramonian, "Fast Asynchronous Algorithms for Shared Memory Parallel Computers," Tech. Rep. CSE-89-8, Univ. of California-Daviz, pp. 1- 17, july 25, 1989.Google ScholarGoogle Scholar
  16. MSP90.C. Martel, It. Subramonian, and A. Park, "Asynchronous PRAMs are (Almost) as Good as Synchronous PRAMs," Proc. 3#nd IEEE Syrup. on Foundations of Computer Science, pp. 590-599, 1990.Google ScholarGoogle Scholar
  17. Ni90.N. Nishimura, "Asynchronous Shared Memory Parallel Computations," Proc. Snd Annual A CM Syrup. on Parallel Algorithms and Architectures, pp. 76-84, 1990. Google ScholarGoogle ScholarDigital LibraryDigital Library
  18. Rab89.M. Rabin, "Efficient Dispersal of informatio'n for Security, Load Balancing and Fault Tolerance," JACM, vol. 30, no. 2, pp. 335- 348, 1989. Google ScholarGoogle ScholarDigital LibraryDigital Library
  19. Ran87.A. Ranade, "How to Emulate Shared Memory," Proc. 28th IEEE Symp. on Foundation8 of Computer Science, pp. 185-194, 1987.Google ScholarGoogle Scholar
  20. Sh89.A. Shvartsman, "Achieving Optimal CRCW Fault-tolerance," Tech. Rep. CS-89-#9, Brown Univ., pp. 1-8, December 22, 1989. Google ScholarGoogle ScholarDigital LibraryDigital Library
  21. ST90.D. Shasha and J. Turek, "Beyond Fail-stop: Wait-free SeriMizability and Resiliency in the Presence of Slow-down Failures,# Tech. Rep. 51#, Dept. of Computer Science, New York Univ., pp. 1-22, September, 1990. Google ScholarGoogle ScholarDigital LibraryDigital Library
  22. Va90.L. Valiant, "A Bridging Model for Parallel Computation," CA CM, vol. 33, no. 8, pp. 103-111, 1990. Google ScholarGoogle ScholarDigital LibraryDigital Library

Index Terms

  1. Combining tentative and definite executions for very fast dependable parallel computing

        Recommendations

        Comments

        Login options

        Check if you have access through your login credentials or your institution to get full access on this article.

        Sign in
        • Published in

          cover image ACM Conferences
          STOC '91: Proceedings of the twenty-third annual ACM symposium on Theory of Computing
          January 1991
          572 pages
          ISBN:0897913973
          DOI:10.1145/103418

          Copyright © 1991 ACM

          Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

          Publisher

          Association for Computing Machinery

          New York, NY, United States

          Publication History

          • Published: 3 January 1991

          Permissions

          Request permissions about this article.

          Request Permissions

          Check for updates

          Qualifiers

          • Article

          Acceptance Rates

          Overall Acceptance Rate1,469of4,586submissions,32%

          Upcoming Conference

          STOC '24
          56th Annual ACM Symposium on Theory of Computing (STOC 2024)
          June 24 - 28, 2024
          Vancouver , BC , Canada

        PDF Format

        View or Download as a PDF file.

        PDF

        eReader

        View online with eReader.

        eReader