Consensus in the presence of timing uncertainty

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Consensus in the presence of timing uncertainty: omission and Byzantine failures (extended abstract)

Full text

Pdf (1.24 MB)

Source

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

Montreal, Quebec, Canada

Pages: 125 - 138

Year of Publication: 1991

ISBN:0-89791-439-2

Author

Stephen Ponzio

MIT Laboratory for Computer Science

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): 11, Citation Count: 4

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/112600.112612 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 , Cynthia Dwork , Nancy Lynch , Larry Stockmeyer, Bounds on the time to reach agreement in the presence of timing uncertainty, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.359-369, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103457]
	2	H. Attiya and N. A. Lynch. Time bounds for realtime process control in the presence of timing uncertainty. Proc. 10th IEEE Real-Time Systems Symposium, 1989, pp. 268-284. Also: Technical Memo MIT/LCS/TM-403, Laboratory for Compurer Science, MIT, July 1989.
	3	H. Attiya and M. Mavronicolas. Efficiency of asynchronous vs. semi-synchronous networks, the 28th annual Allerton Conference on Communication, Control and Computing, October 1990.
	4	F. Cristian, H. Aghili, R. Strong and D. Dolev. Atomic broadcast: from simple message diffusion to Byzantine agreement. Proc. 15th Int. Conf. on Fault Tolerant Computing, 1985, pp. 1-7. Also: IBM Research Report R35244, revised October 1989.
	5	B.A. Coan and C. Dwork. Simultaneity is harder than agreement. Proc. 5th IEEE Symp. on Re/M- bility in Distributed Software and Database Systems, 1986, pp. 141-150.
	6	B. Coan and G. Thomas. Agreeing on a leader in real-time. Proc. 11th IEEE Real-Time Systems Symposium, 1990.
	7	Richard A. DeMillo , Nancy A. Lynch , Michael J. Merritt, Cryptographic protocols, Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.383-400, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802214]
	8	Danny Dolev , Cynthia Dwork , Larry Stockmeyer, On the minimal synchronism needed for distributed consensus, Journal of the ACM (JACM), v.34 n.1, p.77-97, Jan. 1987 [doi>10.1145/7531.7533]
	9	D. Dolev, R. Reischuk, and H. R. Strong. Eventual is earlier than immediate. Proceedings of the 23rd IEEE Syrup. on Foundations of Computer Science, 1982, pp. 196-203.
	10	D. Dolev and H. R. Strong. Authenticated algorithms for Byzantine agreement. SIAM JournM on Computing, Vol. 12, No. 3 (November 1983), pp. 656-666.
	11	Cynthia Dwork , Nancy Lynch , Larry Stockmeyer, Consensus in the presence of partial synchrony, Journal of the ACM (JACM), v.35 n.2, p.288-323, April 1988 [doi>10.1145/42282.42283]
	12	C Dwork , Y Moses, Knowledge and common knowledge in a Byzantine environment I: crash failures, Proceedings of the 1986 Conference on Theoretical aspects of reasoning about knowledge, p.149-169, March 1986, Monterey, California, United States
	13	M. Fischer and N. Lynch. A lower bound for the time to assure interactive consistency. Information Processing Letters, Voh 14, No. 4 (June 1982), pp. 183-186.
	14	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]
	15	A. Herzberg , S. Kutten, Fast isolation of arbitrary forwarding faults, Proceedings of the eighth annual ACM Symposium on Principles of distributed computing, p.339-353, June 1989, Edmonton, Alberta, Canada [doi>10.1145/72981.73006]
	16	Leslie Lamport , Robert Shostak , Marshall Pease, The Byzantine Generals Problem, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.3, p.382-401, July 1982 [doi>10.1145/357172.357176]
	17	M. Merritt. Notes on the Dolev-Strong lower bound for Byzantine agreement. Unpublished manuscript, 1985.
	18	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]
	19	S. Ponzio. The Real-time Cost of Timing Uncertainty: Consensus and Failure Detection. SM thesis, Massachusetts Institute of Technology, June 1991.
	20	Barbara Simons , Jennifer L. Welch , Nancy A. Lynch, An Overview of Clock Synchronization, Proceedings of the Asilomar Workshop on Fault-Tolerant Distributed Computing, p.84-96, January 1990
	21	R. Strong, D. Dolev and F. Cristian. New latency bounds for atomic broadcast. 11th IEEE Real- Time Systems Symposium, 1990.
	22	Jennifer Lindelius Welch , Nancy Lynch, A new fault-tolerant algorithm for clock synchronization, Information and Computation, v.77 n.1, p.1-36, April 1988 [doi>10.1016/0890-5401(88)90043-0]

CITED BY 4

	Hagit Attiya , Cynthia Dwork , Nancy Lynch , Larry Stockmeyer, Bounds on the time to reach agreement in the presence of timing uncertainty, Journal of the ACM (JACM), v.41 n.1, p.122-152, Jan. 1994
	Injong Rhee , Jennifer L. Welch, The impact of time on the session problem, Proceedings of the eleventh annual ACM symposium on Principles of distributed computing, p.191-202, August 10-12, 1992, Vancouver, British Columbia, Canada
	Dimitris Michailidis, Fast set agreement in the presence of timing uncertainty, Proceedings of the eighteenth annual ACM symposium on Principles of distributed computing, p.249-256, May 04-06, 1999, Atlanta, Georgia, United States
	Rida A. Bazzi , Gil Neiger, Simplifying fault-tolerance: providing the abstraction of crash failures, Journal of the ACM (JACM), v.48 n.3, p.499-554, May 2001