Performing work efficiently in the presence of faults

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Performing work efficiently in the presence of faults

Full text

Pdf (1.27 MB)

Source

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

Vancouver, British Columbia, Canada

Pages: 91 - 102

Year of Publication: 1992

ISBN:0-89791-495-3

Authors

Cynthia Dwork	IBM Almaden Research Center
Joseph Y. Halpern	IBM Almaden Research Center
Orli Waarts	Stanford University

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): 2, Downloads (12 Months): 14, Citation Count: 10

Additional Information:

references cited by index terms review 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/135419.135439 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	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 [doi>10.1145/93385.93441]
	2	A. Bas-Noy , D. Dolev, Shared-memory vs. message-passing in an asynchronous distributed environment, Proceedings of the eighth annual ACM Symposium on Principles of distributed computing, p.307-318, June 1989, Edmonton, Alberta, Canada [doi>10.1145/72981.73003]
	3	J. Buss and P. Ragde, "Certified Write- All on a Strongly Asynchronous PRAM," manuscript, 1990.
	4	G. Bracha, unpublished manuscript, Department of Computer Science, Cornell University, July 1984.
	5	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]
	6	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 [doi>10.1145/112600.112603]
	7	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 [doi>10.1145/103418.103459]
	8	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]
	9	C. Martel, R. Subramonian, and A. Park, "Asynchronous PRAMs are (Almost) as Good as Synchronous PRAMs," Proc. 32nd IEEE Symposium on Foundations of Computer Science, pp. 590-599, 1991.

CITED BY 10

	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
	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
	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
	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
	Chryssis Georgiou , Alexander Russell , Alex A. Shvartsman, Work-competitive scheduling for cooperative computing with dynamic groups, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, 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
	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
	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
	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
	Shlomi Dolev , Roberto Segala , Alexander Shvartsman, Dynamic load balancing with group communication, Theoretical Computer Science, v.369 n.1, p.348-360, 15 December 2006

INDEX TERMS

Primary Classification:
D. Software
D.4 OPERATING SYSTEMS
D.4.7 Organization and Design
Subjects: Distributed systems

General Terms:
Algorithms, Performance, Theory, Verification

REVIEW

"Clement R. Attanasio : Reviewer"

The authors study this situation: t machines are available to perform n units of idempotent work; the machines execute synchronously, so the absence of < more...

Collaborative Colleagues:

Cynthia Dwork: colleagues

Joseph Y. Halpern: colleagues

Orli Waarts: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player