Combining tentative and definite executions for very fast dependable parallel computing

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Combining tentative and definite executions for very fast dependable parallel computing

Full text

Pdf (987 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-third annual ACM symposium on Theory of computing table of contents

New Orleans, Louisiana, United States

Pages: 381 - 390

Year of Publication: 1991

ISBN:0-89791-397-3

Authors

Z. M. Kedem	Ecole des Hautes Etudes en Informatique, Université René Descartes, 45, rue des Saints-Pères, 75006 Paris, France and Department of Computer Science, New York University, 251 Mercer St., New York, NY
K. V. Palem	IBM Research Division, T. J. Watson Research Center, P. O. Box 704, Yorktown Heights, NY
A. Raghunathan	Computer Science Division, University of California, Davis, CA and New York University
P. G. Spirakis	Computer Technology Institute, Patras University, P. O. Box 1122, 26110 Patras, Greece

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 15, Citation Count: 27

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/103418.103459 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.

	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.
	AHU74	Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
	BHG87	Philip A. Bernstein , Vassco Hadzilacos , Nathan Goodman, Concurrency control and recovery in database systems, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1987
	Br74	Richard P. Brent, The Parallel Evaluation of General Arithmetic Expressions, Journal of the ACM (JACM), v.21 n.2, p.201-206, April 1974 [doi>10.1145/321812.321815]
	CDR86	Stephen Cook , Cynthia Dwork , Ru&duml;ger Reischuk, Upper and lower time bounds for parallel random access machines without simultaneous writes, SIAM Journal on Computing, v.15 n.1, p.87-97, Feb. 1986 [doi>10.1137/0215006]
	CGM88	W. Cellary , E. Gelenbe , T. Morzy, Concurrency control in distributed database systems, Elsevier Science Inc., New York, NY, 1988
	CZ89	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]
	CZ90	R. Cole , O. Zajicek, The expected advantage of asynchrony, Proceedings of the second annual ACM symposium on Parallel algorithms and architectures, p.85-94, July 02-06, 1990, Island of Crete, Greece [doi>10.1145/97444.97673]
	FW78	Steven Fortune , James Wyllie, Parallelism in random access machines, Proceedings of the tenth annual ACM symposium on Theory of computing, p.114-118, May 01-03, 1978, San Diego, California, United States [doi>10.1145/800133.804339]
	Gi89	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]
	Je90	David Jefferson, Virtual time II: storage management in conservative and optimistic systems, Proceedings of the ninth annual ACM symposium on Principles of distributed computing, p.75-89, August 22-24, 1990, Quebec City, Quebec, Canada [doi>10.1145/93385.93403]
	KS89	P. C. Kanellakis , A. A. Shvartsman, Efficient parallel algorithms can be made robust, Proceedings of the eighth annual ACM Symposium on Principles of distributed computing, p.211-219, June 1989, Edmonton, Alberta, Canada [doi>10.1145/72981.72996]
	KS90	P. Kaaellakis and A. Shvartsman, "On Efficient Parallel Algorithms in the Presence of Omission Errors,# Unpnblished manuscript, October 9, 1990.
	KPS90	Z. M. Kedem , K. V. Palem , P. G. Spirakis, Efficient robust parallel computations, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.138-148, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100231]
	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.
	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.
	Ni90	N. Nishimura, Asynchronous shared memory parallel computation, Proceedings of the second annual ACM symposium on Parallel algorithms and architectures, p.76-84, July 02-06, 1990, Island of Crete, Greece [doi>10.1145/97444.97672]
	Rab89	Michael O. Rabin, Efficient dispersal of information for security, load balancing, and fault tolerance, Journal of the ACM (JACM), v.36 n.2, p.335-348, April 1989 [doi>10.1145/62044.62050]
	Ran87	A. Ranade, "How to Emulate Shared Memory," Proc. 28th IEEE Symp. on Foundation8 of Computer Science, pp. 185-194, 1987.
	Sh89	Alex A. Shvartsman, Achieving Optimal CRCW PRAM Fault-Tolerance, Brown University, Providence, RI, 1989
	ST90	D. Shasha , J. Turek, Beyond Fail-Stop: Wait-Free Serializability and Resiliency in the Presence of Slow-Down Failures, New York University, New York, NY, 1990
	Va90	Leslie G. Valiant, A bridging model for parallel computation, Communications of the ACM, v.33 n.8, p.103-111, Aug. 1990 [doi>10.1145/79173.79181]

CITED BY 27

	Cynthia Dwork , Joseph Y. Halpern , Orli Waarts, Performing work efficiently in the presence of faults, Proceedings of the eleventh annual ACM symposium on Principles of distributed computing, p.91-102, August 10-12, 1992, Vancouver, British Columbia, Canada
	Ramesh Subramonian, Designing synchronous algorithms for asynchronous processors, Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures, p.189-198, June 29-July 01, 1992, San Diego, California, United States
	Bogdan S. Chlebus , Dariusz R. Kowalski , Andrzej Lingas, The do-all problem in broadcast networks, Proceedings of the twentieth annual ACM symposium on Principles of distributed computing, p.117-127, August 2001, Newport, Rhode Island, United States
	Z. M. Kedem , K. V. Palem , M. O. Rabin , A. Raghunathan, Efficient program transformations for resilient parallel computation via randomization (preliminary version), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.306-317, May 04-06, 1992, Victoria, British Columbia, Canada
	Spyros C. Kontogiannis , Grammati E. Pantziou , Paul G. Spirakis , Moti Yung, “Dynamic-fault-prone BSP”: a paradigm for robust computations in changing environments, Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures, p.37-46, June 28-July 02, 1998, Puerto Vallarta, Mexico
	Yonatan Aumann , Michael A. Bender , Lisa Zhang, Efficient execution of nondeterministic parallel programs on asynchronous systems, Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, p.270-276, June 24-26, 1996, Padua, Italy
	Michael A. Bender , Michael O. Rabin, Scheduling Cilk multithreaded parallel programs on processors of different speeds, Proceedings of the twelfth annual ACM symposium on Parallel algorithms and architectures, p.13-21, July 09-13, 2000, Bar Harbor, Maine, United States
	Yonatan Aumann , Michael Ben-Or, Computing with faulty arrays, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.162-169, May 04-06, 1992, Victoria, British Columbia, Canada
	Paul G. Spirakis , Christos D. Zaroliagis, Distributed algorithm engineering, Experimental algorithmics: from algorithm design to robust and efficient software, Springer-Verlag New York, Inc., New York, NY, 2002
	Grzegorz Malewicz, A work-optimal deterministic algorithm for the asynchronous certified write-all problem, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.255-264, July 13-16, 2003, Boston, Massachusetts
	Chryssis Georgiou , Alexander Russell , Alex A. Shvartsman, distributed cooperation and adversity: complexity trade-offs, Proceedings of the Paris C. Kanellakis memorial workshop on Principles of computing & knowledge: Paris C. Kanellakis memorial workshop on the occasion of his 50th birthday, p.60-71, June 08-08, 2003, San Diego, California, USA
	Paris C. Kanellakis , Dimitrios Michailidis , Alex Allister Shvartsman, Controlling memory access concurrency in efficient fault-tolerant parallel algorithms, Nordic Journal of Computing, v.2 n.2, p.146-180, Summer 1995
	Dariusz R. Kowalski , Alex A. Shvartsman, Performing work with asynchronous processors: message-delay-sensitive bounds, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.265-274, July 13-16, 2003, Boston, Massachusetts
	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
	Spyros C. Kontogiannis , Grammati E. Pantziou , Paul G. Spirakis, Efficient computations on fault-prone BSP machines, Proceedings of the ninth annual ACM symposium on Parallel algorithms and architectures, p.84-93, June 23-25, 1997, Newport, Rhode Island, United States
	Chryssis Georgiou , Alexander Russell , Alex A. Shvartsman, The complexity of synchronous iterative Do-All with crashes, Distributed Computing, v.17 n.1, p.47-63, February 2004
	Jan Friso Groote , Wim H. Hesselink , Sjouke Mauw , Rogier Vermeulen, An algorithm for the asynchronous Write-All problem based on process collision, Distributed Computing, v.14 n.2, p.75-81, April 2001
	Dariusz R. Kowalski , Alexander A. Shvartsman, Writing-all deterministically and optimally using a non-trivial number of asynchronous processors, Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures, June 27-30, 2004, Barcelona, Spain
	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
	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
	Dariusz R. Kowalski , Alex A. Shvartsman, Performing work with asynchronous processors: message-delay-sensitive bounds, Information and Computation, v.203 n.2, p.181-210, December 15, 2005
	Paris C. Kanellakis , Alex A. Shvartsman, Efficient parallel algorithms can be made robust, Distributed Computing, v.5 n.4, p.201-217, April 1992
	Antonio Fernández , Chryssis Georgiou , Alexander Russell , Alex A. Shvartsman, The Do-All problem with Byzantine processor failures, Theoretical Computer Science, v.333 n.3, p.433-454, 3 March 2005
	Michael A. Bender , Cynthia A. Phillips, Scheduling DAGs on asynchronous processors, Proceedings of the nineteenth annual ACM symposium on Parallel algorithms and architectures, June 09-11, 2007, San Diego, California, USA
	Cynthia Dwork, Distributed computing column, ACM SIGACT News, v.27 n.3, p.50-54, Sept. 1996
	Dariusz R. Kowalski , Alexander A. Shvartsman, Writing-all deterministically and optimally using a nontrivial number of asynchronous processors, ACM Transactions on Algorithms (TALG), v.4 n.3, p.1-22, June 2008