Byzantine clock synchronization

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Byzantine clock synchronization

Full text

Pdf (676 KB)

Source

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

Vancouver, British Columbia, Canada

Pages: 68 - 74

Year of Publication: 1984

ISBN:0-89791-143-1

Authors

Leslie Lamport
P. M. Melliar-Smith

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): 5, Downloads (12 Months): 50, Citation Count: 21

Additional Information:

abstract 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/800222.806737 What is a DOI?

ABSTRACT

An informal description is given of three fault-tolerant clock-synchronization algorithms. These algorithms work in the presence of arbitrary kinds of failure, including “two-faced” clocks. Two of the algorithms are derived from Byzantine Generals solutions.

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	D. Dolev. The Byzantine Generals Strike Again. Journal of Algorithms 3, 1 (1982), 14-30.
	2	Danny Dolev , Joe Halpern , H. Raymond Strong, On the possibility and impossibility of achieving clock synchronization, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.504-511, December 1984 [doi>10.1145/800057.808720]
	3	Joseph Y. Halpern , Barbara Simons , Ray Strong , Danny Dolev, Fault-tolerant clock synchronization, Proceedings of the third annual ACM symposium on Principles of distributed computing, p.89-102, August 27-29, 1984, Vancouver, British Columbia, Canada [doi>10.1145/800222.806739]
	4	L. Lamport. The Implementation of Reliable Distributed Multiprocess Systems. Computer Networks 2 (1978), 95-114.
	5	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]
	6	Leslie Lamport, Using Time Instead of Timeout for Fault-Tolerant Distributed Systems., ACM Transactions on Programming Languages and Systems (TOPLAS), v.6 n.2, p.254-280, April 1984 [doi>10.1145/2993.2994]
	7	Leslie Lamport , P. M. Melliar-Smith, Synchronizing clocks in the presence of faults, Journal of the ACM (JACM), v.32 n.1, p.52-78, Jan. 1985 [doi>10.1145/2455.2457]
	8	Jennifer Lundelius , Nancy Lynch, A new fault-tolerant algorithm for clock synchronization, Proceedings of the third annual ACM symposium on Principles of distributed computing, p.75-88, August 27-29, 1984, Vancouver, British Columbia, Canada [doi>10.1145/800222.806738]
	9	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]
	10	H. R. Strong and D. Dolev. Byzantine Agreement. Intellectual Leverage for the Information Society (Compcon). IEEE Computer Society Press, New York, 77-82.
	11	J. Wensley et. al. SIFT: Design and Analysis of a Fault-Tolerant Computer for Aircraft Control. Proceedings of the IEEE 66, 10 (Oct. 1978).

CITED BY 21

	B A Coan , D Dolev , C Dwork , L Stockmeyer, The distributed firing squad problem, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.335-345, May 06-08, 1985, Providence, Rhode Island, United States
	Peter Bates, Debugging heterogeneous distributed systems using event-based models of behavior, ACM SIGPLAN Notices, v.24 n.1, p.11-22, Jan. 1989
	Fred B. Schneider, Implementing fault-tolerant services using the state machine approach: a tutorial, ACM Computing Surveys (CSUR), v.22 n.4, p.299-319, Dec. 1990
	Michael Barborak , Anton Dahbura , Minoslaw Malek, The consensus problem in fault-tolerant computing, ACM Computing Surveys (CSUR), v.25 n.2, p.171-220, June 1993
	Joseph Y. Halpern , Barbara Simons , Ray Strong , Danny Dolev, Fault-tolerant clock synchronization, Proceedings of the third annual ACM symposium on Principles of distributed computing, p.89-102, August 27-29, 1984, Vancouver, British Columbia, Canada
	N. Lynch, A hundred impossibility proofs for distributed computing, Proceedings of the eighth annual ACM Symposium on Principles of distributed computing, p.1-28, June 1989, Edmonton, Alberta, Canada
	Frank M. Pittelli , Hector Garcia-Molina, Reliable scheduling in a TMR database system, ACM Transactions on Computer Systems (TOCS), v.7 n.1, p.25-60, Feb. 1989
	Stephen R. Mahaney , Fred B. Schneider, Inexact agreement: accuracy, precision, and graceful degradation, Proceedings of the fourth annual ACM symposium on Principles of distributed computing, p.237-249, August 1985, Minaki, Ontario, Canada
	J Y Halpern , N Megiddo , A A Munshi, Optimal precision in the presence of uncertainty, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.346-355, May 06-08, 1985, Providence, Rhode Island, United States
	Peter C. Bates, Debugging heterogeneous distributed systems using event-based models of behavior, ACM Transactions on Computer Systems (TOCS), v.13 n.1, p.1-31, Feb. 1995
	Hector Garcia Molina , Frank Pittelli , Susan Davidson, Applications of Byzantine agreement in database systems, ACM Transactions on Database Systems (TODS), v.11 n.1, p.27-47, March 1986
	K. -Q. Yan , Y. H. Chin , S. -C. Wang, Optimal Agreement Protocol in Malicious Faulty Processors and Faulty Links, IEEE Transactions on Knowledge and Data Engineering, v.4 n.3, p.266-280, June 1992
	David R. Cheriton, Preliminary thoughts on problem-oriented shared memory: a decentralized approach to distributed systems, ACM SIGOPS Operating Systems Review, v.19 n.4, p.26-33, October 1985
	R. Gusella , S. Zatti, The Accuracy of the Clock Synchronization Achieved by TEMPO in Berkeley UNIX 4.3BSD, IEEE Transactions on Software Engineering, v.15 n.7, p.847-853, July 1989
	K. Arvind, Probabilistic Clock Synchronization in Distributed Systems, IEEE Transactions on Parallel and Distributed Systems, v.5 n.5, p.474-487, May 1994
	Rogério Drummond , Özalp Babaoğlu, Low-cost clock synchronization, Distributed Computing, v.6 n.4, p.193-203, July 1993
	Lidong Zhou , Fred B. Schneider , Robbert Van Renesse, APSS: proactive secret sharing in asynchronous systems, ACM Transactions on Information and System Security (TISSEC), v.8 n.3, p.259-286, August 2005
	Neil W. Rickert, Non-byzantine clock synchronization—a programming experiment, ACM SIGOPS Operating Systems Review, v.22 n.1, p.73-78, Jan., 1988
	Claudio Pinello , Luca P. Carloni , Alberto L. Sangiovanni-Vincentelli, Fault-Tolerant Deployment of Embedded Software for Cost-Sensitive Real-Time Feedback-Control Applications, Proceedings of the conference on Design, automation and test in Europe, p.21164, February 16-20, 2004
	Sirio Scipioni , Leonardo Querzoni , Sara Tucci Piergiovanni , Roberto Baldoni, A theoretical evaluation of peer-to-peer internal clock synchronization, Proceedings of the 2nd International Conference on Autonomic Computing and Communication Systems, p.1-8, September 23-25, 2008, Turin, Italy
	Hui-Ching Hsieh , Jenq-Shiou Leu , Yen-Chiu Chen , Wei-Kuan Shih, Improving fault-tolerant scheme for a time-sensitive autonomous local wireless sensor network, Proceedings of the International Conference on Mobile Technology, Applications, and Systems, September 10-12, 2008, Yilan, Taiwan