Optimal and efficient clock synchronization under drifting clocks

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Optimal and efficient clock synchronization under drifting clocks

Full text

Pdf (1.13 MB)

Source

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

Atlanta, Georgia, United States

Pages: 3 - 12

Year of Publication: 1999

ISBN:1-58113-099-6

Authors

Rafail Ostrovsky	Bellcore, Morristown, NJ
Boaz Patt-Shamir	Dept. of Electrical Engineering-Systems, Tel-Aviv 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): 3, Downloads (12 Months): 34, Citation Count: 3

Additional Information:

references cited by index terms collaborative colleagues peer to peer

Tools and Actions:	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/301308.301316 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	Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
	2	Hagit Attiya , Amir Herzberg , Sergio Rajsbaum, Optimal Clock Synchronization Under Different Delay Assumptions, SIAM Journal on Computing, v.25 n.2, p.369-389, February 1996 [doi>10.1137/S0097539794266328]
	3	Giorgio Ausiello , Giuseppe F. Italiano , Alberto Marchetti Spaccamela , Umberto Nanni, Incremental algorithms for minimal length paths, Journal of Algorithms, v.12 n.4, p.615-638, Dec. 1991 [doi>10.1016/0196-6774(91)90036-X]
	4	A. Borodin and S. Cook. A time-space tradeoff for sorting on a general sequential model of computation. SIAM J. Comput., 11(2):287-297, 1982.
	5	A. Borodin, M. Fischer, D. Kirkpatrick, N. Lynch, and M. Tompa. A time-space tradeoff for sorting on non-oblivious machines. J. Comp. and $yst. Sci., 22:351-364, 1981.
	6	F. Cristian. Probabilistic clock synchronization. Distributed Computing, 3:146-158, 1989.
	7	Danny Dolev , Joseph Y Halpern , Raymond H Strong, On the possibility and impossibility of achieving clock synchronization, Journal of Computer and System Sciences, v.32 n.2, p.230-250, April 1986 [doi>10.1016/0022-0000(86)90028-0]
	8	Danny Dolev , Nancy A. Lynch , Shlomit S. Pinter , Eugene W. Stark , William E. Weihl, Reaching approximate agreement in the presence of faults, Journal of the ACM (JACM), v.33 n.3, p.499-516, July 1986 [doi>10.1145/5925.5931]
	9	Danny Dolev , Rüdiger Reischuk , Ray Strong, Observable clock synchronization extended abstract, Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing, p.284-293, August 14-17, 1994, Los Angeles, California, United States [doi>10.1145/197917.198110]
	10	Colin Fidge, Logical Time in Distributed Computing Systems, Computer, v.24 n.8, p.28-33, August 1991 [doi>10.1109/2.84874 ]
	11	J. Y. Halpern, N. Megiddo, and A. A. Munshi. Optimal precision in the presence of uncertainty. Journal of Complexity, 1:170-196, 1985.
	12	Leslie Lamport, Time, clocks, and the ordering of events in a distributed system, Communications of the ACM, v.21 n.7, p.558-565, July 1978 [doi>10.1145/359545.359563]
	13	J. Lundelius and N. Lynch. An upper and lower bound for clock synchronization. Information and Computation, 62(2-3):190-204, 1984.
	14	Keith Marzullo , Susan Owicki, Maintaining the time in a distributed system, Proceedings of the second annual ACM symposium on Principles of distributed computing, p.295-305, August 17-19, 1983, Montreal, Quebec, Canada [doi>10.1145/800221.806730]
	15	F. Mattern. Virtual time and global states of distributed systems. In M. Cosnard, editor, Proc. International Workshop on Parallel ~ Distributed Algorithms, pages 215-226, 1989.
	16	D. L. Mills. Internet time synchronization: the Network Time Protocol. IEEE 7Yans. Comm., 39(10):1482-1493, Oct. 1991.
	17	D. L. Mills. The Network Time Protocol (version 3): Specification, implementation and analysis. RFC 1305, Network Working Group, University of Delaware, Mar. 1992.
	18	Yoram Moses , Ben Bloom, Knowledge, timed precedence and clocks (preliminary report), Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing, p.294-303, August 14-17, 1994, Los Angeles, California, United States [doi>10.1145/197917.198113]
	19	J. Palsetia. Analysis of clock synchronization algorithms. MSc project, Dept. of Electrical and Computer Engineering, Northeastern University, May 1997.
	20	B. Patt-Shamir. A Theory of Clock Synchronization. PhD thesis, MIT Lab. for Computer Science, Oct. 1994.
	21	Boaz Patt-Shamir , Sergio Rajsbaum, A theory of clock synchronization (extended abstract), Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.810-819, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195466]
	22	Fred B. Schneider, Understanding Protocols for Byzantine Clock Synchronization, Cornell University, Ithaca, NY, 1987
	23	B. Simons, J. L. Welch, and N. Lynch. An overview of clock synchronization. Research Report RC 6505 (63306), IBM, 1988.
	24	A. P. Sistla , J. L. Welch, Efficient distributed recovery using message logging, Proceedings of the eighth annual ACM Symposium on Principles of distributed computing, p.223-238, June 1989, Edmonton, Alberta, Canada [doi>10.1145/72981.72997]
	25	T. K. Srikanth , Sam Toueg, Optimal clock synchronization, Journal of the ACM (JACM), v.34 n.3, p.626-645, July 1987 [doi>10.1145/28869.28876]

CITED BY 3

	Rui Fan , Nancy Lynch, Gradient clock synchronization, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada
	Rui Fan , Nancy Lynch, Gradient clock synchronization, Distributed Computing, v.18 n.4, p.255-266, March 2006
	David Bauer , Garrett Yaun , Christopher D. Carothers , Murat Yuksel , Shivkumar Kalyanaraman, Seven-O'Clock: A New Distributed GVT Algorithm Using Network Atomic Operations, Proceedings of the 19th Workshop on Principles of Advanced and Distributed Simulation, p.39-48, June 01-03, 2005