Efficient robust parallel computations

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Efficient robust parallel computations

Full text

Pdf (983 KB)

Source

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

Baltimore, Maryland, United States

Pages: 138 - 148

Year of Publication: 1990

ISBN:0-89791-361-2

Authors

Z. M. Kedem	Department of Computer Science, Courant Institute of Mathematical Sciences, 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
P. G. Spirakis	Computer Technology Institute, Patras University, Patras, P. O. Box 1122, 26110 Patras

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 0, Downloads (12 Months): 14, Citation Count: 34

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/100216.100231 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.

	Aw88	B. Awerbuch, "On the effects of feedback in dynamic network protocols," Proc. 29th IEEE FOCS, pp. 231-242, 1988.
	AAG87	Y. Afek, B. Awerbuch, and E. Gafni, "Applying static network protocols to dynamic networks," Proc. 28th IEEE FOCS, pp. 358- 370, 1987.
	AAPS87	Y. Afek, B. Awerbuch, S. Plotkin, and M. Saks, "Local management of a global resource in a communication network," Proc. 28th IEEE FOCS, pp. 347-357, 1987.
	AHU74	Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
	AS88	B. Awerbuch and M. Sipser, "Dynamic networks are as fast as static networks," Proc. 29th IEEE FOCS, pp. 206-219, 1988.
	B74	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]
	Ch52	H. Chernoff, "A measure of asymptotic efficiency for test of a hypothesis based on the sum of observations," Annals of Math. Stat., vol. 23, pp. 493-509, 1952.
	Co86	R. Cole, "Parallel merge sort," Proc. 27th IEEE FOCS, pp. 511-516, 1986.
	CV86	R. Cole and U. Vishkin, "Approximate and exact parallel scheduling with application to list, tree, and graph problems," Proc. 27th IEEE FOCS, pp. 468-491, 1986.
	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]
	DPPU86	C Dwork , D Peleg , N Pippenger , E Upfal, Fault tolerance in networks of bounded degree, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.370-379, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12169]
	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]
	Kh89	S. Khuller, private communication, June 1989.
	KLP89	Z. M. Kedem , G. M. Landau , K. V. Palem, Optimal parallel suffix-prefix matching algorithm and applications, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.388-398, June 18-21, 1989, Santa Fe, New Mexico, United States [doi>10.1145/72935.72977]
	KP88	Zvi M. Kedem , Krishna V. Palem, Optimal parallel algorithms for forest and term matching, Theoretical Computer Science, v.93 n.2, p.245-264, 17 Feb. 1992 [doi>10.1016/0304-3975(92)90332-A]
	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]
	MPS89	C. Martel, A. Park, and R. Subramonian, "Fast asynchronous algorithms for shared memory parallel computers," Tech. Rep. CSE-89-8, Univ. of California - Davis, pp. 1-17, July 25, 1989.
	Pi85	N. Pippinger, "On networks of noisy gates," Proc. 26th IEEE FOCS, pp. 30-38, 1985.
	SS83	Richard D. Schlichting , Fred B. Schneider, Fail-stop processors: an approach to designing fault-tolerant computing systems, ACM Transactions on Computer Systems (TOCS), v.1 n.3, p.222-238, August 1983 [doi>10.1145/357369.357371]
	Sh89	Alex A. Shvartsman, Achieving Optimal CRCW PRAM Fault-Tolerance, Brown University, Providence, RI, 1989
	TV84	R. Tarjan and U. Vishkin, "Finding biconnected components and computing tree functions in logarithmic parallel time," Proc. 25th IEEE FOCS, pp. 12-22, 1984.

CITED BY 34

	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
	Paris C. Kanellakis , Alex A. Shvartsman, Efficient parallel algorithms on restartable fail-stop processors, Proceedings of the tenth annual ACM symposium on Principles of distributed computing, p.23-36, August 19-21, 1991, Montreal, Quebec, 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 , Stefan Dobrev , Dariusz R. Kowalski , Grzegorz Malewicz , Alex Shvartsman , Imrich Vrto, Towards practical deteministic write-all algorithms, Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures, p.271-280, July 2001, Crete Island, Greece
	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
	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
	David Culler , Richard Karp , David Patterson , Abhijit Sahay , Klaus Erik Schauser , Eunice Santos , Ramesh Subramonian , Thorsten von Eicken, LogP: towards a realistic model of parallel computation, ACM SIGPLAN Notices, v.28 n.7, p.1-12, July 1993
	Hagit Attiya , Nancy Lynch , Nir Shavit, Are wait-free algorithms fast?, Journal of the ACM (JACM), v.41 n.4, p.725-763, July 1994
	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
	Nir Shavit , Eli Upfal , Asaph Zemach, A wait-free sorting algorithm, Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing, p.121-128, August 21-24, 1997, Santa Barbara, California, United States
	Greg Barnes, A method for implementing lock-free shared-data structures, Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures, p.261-270, June 30-July 02, 1993, Velen, Germany
	Z. M. Kedem , K. V. Palem , A. Raghunathan , P. G. Spirakis, Combining tentative and definite executions for very fast dependable parallel computing, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.381-390, May 05-08, 1991, New Orleans, Louisiana, United States
	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
	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
	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
	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
	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
	Andrea C. Dusseau , David E. Culler , Klaus Erik Schauser , Richard P. Martin, Fast Parallel Sorting Under LogP: Experience with the CM-5, IEEE Transactions on Parallel and Distributed Systems, v.7 n.8, p.791-805, August 1996
	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
	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 , Roberto De Prisco , Alex A. Shvartsman, Performing tasks on synchronous restartable message-passing processors, Distributed Computing, v.14 n.1, p.49-64, January 2001
	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
	Paris C. Kanellakis , Alex A. Shvartsman, Efficient parallel algorithms can be made robust, Distributed Computing, v.5 n.4, p.201-217, April 1992
	Naomi Nishimura, Asynchronous shared memory parallel computation (preliminary version), ACM SIGARCH Computer Architecture News, v.19 n.1, p.97-105, March 1991
	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
	Fangzhe Chang , Vijay Karamcheti, A Framework for Automatic Adaptation of Tunable Distributed Applications, Cluster Computing, v.4 n.1, p.49-62, March 2001
	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