Time-optimal message-efficient work performance in the presence of faults

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Time-optimal message-efficient work performance in the presence of faults

Full text

Pdf (1.13 MB)

Source

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

Los Angeles, California, United States

Pages: 161 - 172

Year of Publication: 1994

ISBN:0-89791-654-9

Authors

Roberto De Prisco	Dept. of Computer Science, Columbia University, New York, NY and Dipartimento di Informatica ed Applicazioni, Università di Salerno, 84081 Baronissi (SA), Italy
Alain Mayer	Dept. of Computer Science, Columbia University, New York, NY
Moti Yung	IBM Research Division T.J. Watson Research Center, Yorktown Heights, NY

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): 1, Downloads (12 Months): 9, Citation Count: 18

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

	AHW92	Eugene S. Amdur , Samuel M. Weber , Vassos Hadzilacos, On the message complexity of binary byzantine agreement under crash failures, Distributed Computing, v.5 n.4, p.175-186, April 1992 [doi>10.1007/BF02277665]
	RSA-129	D. Atkins, M. Graft, A. Lenstra, and P. Leyland, Internet announcement, April, 1994.
	CMY94	T.D. Chandra, A. Mayer, and M. Yung, Subquadratic-Message Early-Stopping Fail- Stop Agreement. manuscript in preparation.
	CT90	Tushar Deepak Chandra , Sam Toueg, Time and message efficient reliable broadcasts, Proceedings of the 4th international workshop on Distributed algorithms, p.289-303, June 1991, Bari, Italy
	DRS90	Danny Dolev , Ruediger Reischuk , H. Raymond Strong, Early stopping in Byzantine agreement, Journal of the ACM (JACM), v.37 n.4, p.720-741, Oct. 1990 [doi>10.1145/96559.96565]
	DHW92	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 [doi>10.1145/135419.135439]
	DHW93	Full version of DHW92 (preprint), Personal Communication by J. H alpern.
	FBCL91	Michael J. Feeley , Brian N. Bershad , Jeffrey S. Chase , Henry M. Levy, Dynamic node reconfiguration in a parallel-distributed environment, Proceedings of the third ACM SIGPLAN symposium on Principles and practice of parallel programming, p.114-121, April 21-24, 1991, Williamsburg, Virginia, United States
	HH93	Vassos Hadzilacos , Joseph Y. Halpern, Message-optimal protocols for byzantine agreement (extended abstract), Proceedings of the tenth annual ACM symposium on Principles of distributed computing, p.309-323, August 19-21, 1991, Montreal, Quebec, Canada [doi>10.1145/112600.112626]
	Kam94	David Louts Kaminsky, Adaptive parallelism with Piranha, Yale University, New Haven, CT, 1995
	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]
	LM89	Arjen K. Lenstra , Mark S. Manasse, Factoring by electronic mail, Proceedings of the workshop on the theory and application of cryptographic techniques on Advances in cryptology, p.355-371, November 1990, Houthalen, Belgium
	LLM88	M. Litzkow, M. Livny and M. Mutka, Condora Hunter of Idle Workstations. Proc. 8th Int. Syrup. on Distributed Computing Systems. 1988
	Si90	Robert D. Silverman, Massively distributed computing and factoring large integers, Communications of the ACM, v.34 n.11, p.95-103, Nov. 1991 [doi>10.1145/125490.125504]
	TLC85	Marvin M. Theimer , Keith A. Lantz , David R. Cheriton, Preemptable remote execution facilities for the V-system, Proceedings of the tenth ACM symposium on Operating systems principles, p.2-12, December 1985, Orcas Island, Washington, United States

CITED BY 18

	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
	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
	Grzegorz Greg Malewicz , Alexander Russell , Alex Shvartsman, Optimal scheduling for disconnected cooperation, Proceedings of the twentieth annual ACM symposium on Principles of distributed computing, p.305-307, August 2001, Newport, Rhode Island, 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 , Alex A. Shvartsman, Cooperative computing with fragmentable and mergeable groups, Journal of Discrete Algorithms, v.1 n.2, p.211-235, April 2003
	Bogdan S. Chlebus , Dariusz R. Kowalski, Randomization helps to perform independent tasks reliably, Random Structures & Algorithms, v.24 n.1, p.11-41, January 2004
	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
	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
	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
	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
	Chryssis Georgiou , Dariusz R. Kowalski , Alexander A. Shvartsman, Efficient gossip and robust distributed computation, Theoretical Computer Science, v.347 n.1-2, p.130-166, 30 November 2005
	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
	Bogdan S. Chlebus , Leszek Gasieniec , Dariusz R. Kowalski , Alex A. Shvartsman, A robust randomized algorithm to perform independent tasks, Journal of Discrete Algorithms, v.6 n.4, p.651-665, December, 2008
	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