Efficient parallel algorithms can be made robust

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Efficient parallel algorithms can be made robust

Full text

Pdf (1.17 MB)

Source

Annual ACM Symposium on Principles of Distributed Computing archive
Proceedings of the eighth annual ACM Symposium on Principles of distributed computing table of contents

Edmonton, Alberta, Canada

Pages: 211 - 219

Year of Publication: 1989

ISBN:0-89791-326-4

Authors

P. C. Kanellakis	INRIA / Altaïr, BP 105, Rocquencourt 78159 Le Chesnay Cedex, FRANCE
A. A. Shvartsman	Department of Computer Science, Brown University, PO Box 1910, Providence, RI

Sponsors

SIGOPS: ACM Special Interest Group on Operating Systems
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 0, Downloads (12 Months): 9, Citation Count: 28

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

	A 88	B. Awerbuch, "On the effects of feedback in dynamic network protocols", in Proc. of the 29~h IEEE FOCS, pp. 231-242, 1988.
	AAG 87	Y. Afek, B. Awerbuch, E. Gafni, "Applying static network protocols to dynamic networks", in Proc. of the 28th IEEE FOCS, pp. 358-370, 1987.
	AAPS 87	Y. Afek, B. Awerbuch, S. Plotkin, M. Saks, "Local management of a global resource in a communication network", in Proc. of the PSth IEEE FOCS, pp. 347-357, 1987.
	AS 88	B. Awerbuch, M. Sipser, "Dynamic networks are as fast as static networks", in Proc. of the 29th IEEE FOCS, pp. 206-219, 1988.
	B 68	K.E. Batcher, "Sorting networks and their applications", iu Proc. of the AFIPS Spring Joint Comp. Conf., vol. 32, pp. 307-314, 1968.
	B 78	Gérard M. Baudet, Asynchronous Iterative Methods for Multiprocessors, Journal of the ACM (JACM), v.25 n.2, p.226-244, April 1978 [doi>10.1145/322063.322067]
	B 88	B. Bloom, Constructing Two-Writer Atomic Registers, IEEE Transactions on Computers, v.37 n.12, p.1506-1514, December 1988 [doi>10.1109/12.9729]
	DDS 83	D. Dolev, C. Dwork, L. Stockmeyer, "On the minimal synchronism needed for distributed consensus", in Proc. of the ~th IEEE FOCS, pp. 393--402, 1983.
	DPPU 86	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]
	F 83	M. J. Fischer, "The consensus problem in unreliable distributed systems (a brief survey)", Yale Univ. Tech. Rep., DCS/RR-273, 1983.
	FL 82	M. J. Fischer and N. A. Lynch, "A lower bound for the time to assure interactive consistency", IPL, vol. 14., no. 4, pp. 183-186, 1982.
	FLP 85	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]
	FW 78	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]
	LGFG 86	Nancy A Lynch , Nancy D Griffeth , Michael J Fishcher , Leonidas J Guibas, Probabilistic analysis of a network resource allocation algorithm, Information and Control, v.68 n.1-3, p.47-85, Jan/Feb/March 1986 [doi>10.1016/S0019-9958(86)80028-6]
	P 85	N. Pippinger, "On networks of noisy gates", in Proc. of the 26ih IEEE FOCS, pp. 30-38, 1985.
	PSL 80	M. Pease , R. Shostak , L. Lamport, Reaching Agreement in the Presence of Faults, Journal of the ACM (JACM), v.27 n.2, p.228-234, April 1980 [doi>10.1145/322186.322188]
	R 85	L. Rudolph, "A robust sorting network", IEEE Trans. on Comp., vol. c-34, no. 4, pp. 326-335, 1985.
	S 83	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]
	TV 84	R. E. Tarjan, U. Vishkin, "Finding biconnected components and computing tree functions in logarithmic parallel time", in Proc. of lhc 25th IEEE FOCS, pp. 12-22, 1984.

CITED BY 28

	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
	Serge Abiteboul , Gabriel M. Kuper , Harry G. Mairson , Alexander A. Shvartsman , Moshe Y. Vardi, In memoriam Paris C. Kanellakis, ACM Computing Surveys (CSUR), v.28 n.1, p.3-15, March 1996
	Roberto De Prisco , Alain Mayer , Moti Yung, Time-optimal message-efficient work performance in the presence of faults, Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing, p.161-172, August 14-17, 1994, Los Angeles, 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
	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
	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
	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
	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
	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
	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
	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
	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
	Serge Abiteboul , Gabriel M. Kuper , Harry G. Mairson , Alexander A. Shvartsman , Moshe Y. Vardi, In Memoriam: Paris C. Kanellakis, 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.1-8, June 08-08, 2003, San Diego, California, USA
	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
	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
	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
	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
	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
	Cynthia Dwork, Distributed computing column, ACM SIGACT News, v.27 n.3, p.50-54, Sept. 1996