pfluegl@copland.eng.uci.edu (Manfred J. Pfluegl) (06/01/91)
Hi,
Last week I posted a request for references to papers that discuss
issues of clock synchronization in not-completely connected networks
without the use of Byzantine agreement and authentication.
I already posted one short follow-up but meanwhile
I got several more emails asking me for a summary of received references
and of references to general clock synchronization.
I also added some papers that I think are relevant in this area.
If you know of any articles that are concerned w/ clock synchronization in
not completely connected networks and do not use Byzantine Agreement,
I (and others) would appreciate your input. Please post or email.
Thanks a lot in advance, Manfred
Please note that the following list contains many references
of clock synchronization in completely connected networks and of
algorithms using Byzantine agreement or signatures.
--- cut here ---
There are several
RFC's (request for comment, a technical paper usually proposing some
new standard or revision of an old one) available on uunet.uu.net
discussing NTP, the Network Time Protocol. NTP is commonly used to
synchronize the clocks on different machines, and to keep them ticking
at the same rate by adjusting the rate at which they tick. When one
or more machines is connected to some authorative time source (WWV receiver,
atmoic clock, GOES receiver, etc), NTP can be used to keep clocks
aligned with "true" time.
The general problem of clock synchronization and NTP's approach to
solving it have been investigated in great detail in several RFC's.
The specific RFC's discussing NTP are 1129, 1165, 1128, 1119, 1059, 958.
RFC 1129 is probably the best place to start. RFC's in general
are numbered sequentially so higher numbers indicate newer publications,
with some of them being rewrites of earlier RFC's.
Also see the Usenet newsgroup comp.protocols.time.ntp, which is
a news version of the mailing list accessed as ntp@trantor.umd.edu .
@string{ftcs13 = "13th Fault-Tolerant Computing Symposium"}
@string{ftcs14 = "14th Fault-Tolerant Computing Symposium"}
@string{ftcs15 = "15th Fault-Tolerant Computing Symposium"}
@string{ftcs16 = "16th Fault-Tolerant Computing Symposium"}
@string{ftcs17 = "17th Fault-Tolerant Computing Symposium"}
@string{ftcs18 = "18th Fault-Tolerant Computing Symposium"}
@string{ftcs19 = "19th Fault-Tolerant Computing Symposium"}
@string{ftcs20 = "20th Fault-Tolerant Computing Symposium"}
@string{ftcs21 = "21th Fault-Tolerant Computing Symposium"}
@string{prfts91= "The 1991 Pacific Rim International Symposium on Fault-Tolerant Systems"}
@string{dcs9 = "Proceedings of the 9th International Conference on Distributed Computing Systems"}
@string{sigact3 = "Proceedings of the 3rd ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing"}
@string{sigact4 = "Proceedings of the 4th ACM SIGACT-SIGOPS Symposium, Principles in Distributed Computing"}
@string{reliable3 = "Proceedings of the 3th Symposium on Reliability in Distributed Software and Database Systems"}
@string{reliable9 = "Proceedings of the 9th Symposium on Reliable Distributed Systems"}
@string{acmspdc2 = "Proceedings of the 2nd ACM Symposium on Principles of Distributed Computing"}
@string{ieeetc = "IEEE Transactions On Computers"}
@string{ieeetse = "IEEE Transactions On Software Engineering"}
@string{jacm = "Journal of the ACM"}
@string{ja = "Journal of Algorithms"}
@string{cacm = "Communications of the ACM"}
@string{ic = "Information and Control"}
@string{infcomp= "Information and Computation"}
@string{ieee = "IEEE"}
@string{acm = "ACM"}
@inproceedings{
mahaney:inexact,
author = "S. Mohaney and F. Schneider",
title = "Inexact Agreement: Accuracy, Precision, and Graceful Degradation",
booktitle = sigact4,
month = aug,
year = 1985,
organization = ACM,
pages = "237-249"}
@inproceedings{
thambidurai:clock,
author = "P. Thambidurai and A.M. Finn and R.M. Kieckhafer and C.J. Walter",
title = "Clock Synchronization in {MAFT}",
booktitle = ftcs19,
month = jun,
year = 1989,
organization = IEEE,
pages = "142-149"}
@inproceedings{
cristian:probabilistic,
author = "Flaviu Cristian",
title = "A Probabilistic Approach to Distributed Clock Synchronization",
booktitle = dcs9,
year = 1989,
organization = IEEE,
pages = "288-295"}
@article{
lamport:synchronizing,
author = "Lamport, Leslie and P.M. Melliar-Smith",
title = "Synchronizing Clocks in the Presence of Faults",
journal = jacm,
volume = 21,
month = jan,
year = 1985,
pages = "52-78"}
@article{
lamport:time,
author = "Lamport, Leslie",
title = "Time, Clocks, and the Ordering of Events in a Distributed System",
journal = cacm,
volume = 32,
number = 7,
month = jul,
year = 1978,
pages = "558-565"}
@article{
kopetz:clock,
author = "H. Kopetz and W. Ochsenreiter",
title = "Clock Synchronization in Distributed Real-Time Systems",
journal = ieeetc,
volume = "C--36",
number = 8,
month = aug,
year = 1987,
pages = "933-940"}
@article{
srikanth:optimal,
author = "T.K. Srikanth and S. Toueg",
title = "Optimal Clock Synchronization",
journal = jacm,
volume = 34,
number = 3,
month = jul,
year = 1987,
pages = "626-645"}
@article{
gusella:accuracy,
author = "R. Gusella and S. Zatti",
title = "The Accuracy of the Clock Synchronization Achieved by {TEMPO} in {Berkeley UNIX 4.3BSD}",
journal = "Report No. UCB/CSD 87/337, Computer Science Division, {\rm University of California, Berkeley, USA}",
month = jan,
year = 1987}
@article{
pfluegl:general,
author = "Manfred Pfluegl and Douglas Blough",
title = "A General Probabilistic Clock Synchronization Model and a {``Sliding Window'' Convergence Function}",
journal = "Techn. Report No. ECE--90--21, Electrical and Computer Engineering, {\rm University of California, Irvine, USA}",
month = oct,
year = 1990}
@article{
pfluegl:worstcase,
author = "Manfred Pfluegl and Douglas Blough",
title = "Worst-Case Analysis of the {Sliding Window Clock Synchronization Algorithm}",
journal = "Techn. Report No. ECE--91--04, Electrical and Computer Engineering, {\rm University of California, Irvine, USA}",
month = june,
year = 1991}
@inproceedings{
pfluegl:new,
author = "Manfred Pfluegl and Douglas Blough",
title = "A New Model and Simulation Tool for Fault-Tolerant Clock Synchronization",
booktitle = "Proceedings of the 22nd Annual Pittsburgh Conference on Modeling and Simulation",
volume = "22",
organization = "Instrument Society of America",
month = may,
year = 1991}
@inproceedings{
pfluegl:fault,
author = "Manfred Pfluegl and Douglas Blough",
title = "Evaluation of a New Algorithm for Fault-Tolerant Clock Synchronization",
booktitle = prfts91,
organization = "The Institute of Electronics, Information and Communication Engineers",
month = sep,
year = 1991}
@article{
lundeliuswelch:new,
author = "Lundelius Welch, J. and Lynch, N.",
title = "A New Fault-Tolerant Algorithm for Clock Synchonization",
journal = infcomp,
volume = "77",
number = 1,
month = apr,
year = 1988,
organization = "Academic Press",
pages = "1-36"}
@article{
dolev:byzantine,
author = "D. Dolev",
title = "The Byzantine Generals Strike Again",
journal = ja,
organization = "Academic Press",
year = 1982,
pages = "14-30"}
%month = jul,
%volume = 3,
@inproceedings{
lundelius:new,
author = "Lundelius, J. and Lynch, N.",
title = "A New Fault-Tolerant Algorithm for Clock Synchonization",
booktitle = sigact3,
month = aug,
year = 1984,
organization = ACM,
pages = "75-88"}
@inproceedings{
halpern:fault,
author = "Halpern, J., Simons, B., Strong, R., and Dolev, D.",
title = "Fault-Tolerant Clock Synchonization",
booktitle = sigact3,
month = aug,
year = 1984,
organization = ACM,
pages = "89-102"}
@inproceedings{
marzullo:maintaining,
author = "K.A. Marzullo and S. Owicki",
title = "Maintaining the Time in a Distributed System",
booktitle = acmspdc2,
month = aug,
year = 1983,
organization = ACM,
pages = "295-305"}
@inproceedings{
dolev:reaching,
author = "D. Dolev and N.A. Lynch and S.S. Pinter and E.W. Stark and W.E. Weihl",
title = "Reaching Approximate Agreement in the Presence of Faults",
booktitle = reliable3,
month = oct,
year = 1983,
pages = "145-154"}
@phdthesis{
schwabl:einfluss,
author = "Schwabl, Wolfgang",
title = "Der Einfluss Zufaelliger und Systematischer Fehler auf die Uhrensynchronisation in Verteilten Echtzeitsystemen",
school = "Technische Universitaet Wien",
address = "Vienna, Austria",
month = oct,
year = 1989}
@article{COLE88clock,
key = {COLE 88},
author = {Cole, R. and Foxcroft, C.},
title = {An Experiment in Clock Synchronization},
journal = {The Computer Journal},
volume = {31},
number = {6},
pages = {496--502},
month = jun,
year = {1988}
}
@article{MILL90ccra,
key = {MILL 90},
author = {Mills, D. L.},
title = {On the Accuracy and Stability of Clocks Synchronized by the
Network Time Protocol in the Internet System},
journal = {Computer Communication Review},
volume = {20},
number = {1},
pages = {65-75},
month = jan,
year = {1990},
field = {Synchronization},
abstract = {Shows how to accurately synchronize colcks in a very large
internet.}
}
@inproceedings{OFEK89dcs,
key = {OFEK 89},
author = {Ofek, Y.},
title = {Generating a Fault Tolerant Global Clock in a High Speed
Distributed System},
booktitle = {Proc.~9th Int.~Conf.~on Distributed Computing Systems},
month = jun,
year = {1989},
address = {San Jose, CA},
pages = {218--226},
field = {Synchronization},
abstract = {Describes a sychr. scheme that uses HW and achieves a
precision in the microsec range if neighbors exchange sync messages
every microsec.}
}
@article{RAMA90clock,
key = {RAMA 90},
author = {Ramanathan, P. and Shin, K. and Butler, R.~W.},
title = {Fault-Tolerant Clock Synchronization in Distributed Systems},
journal = {Computer},
volume = {23},
number = {10},
pages = {33--42},
month = oct,
year = {1990},
field = {CM, clock},
abstract = {Gives a good survey on the various clock synchronization
techniques and has a clean notation.}
}
@inproceedings{SCHM90clock,
key = {SCHM 90},
author = {Schmuck, F. and Cristian, F.},
title = {Continuous Clock Amortization Need Not Affect the Precision
of a Clock Synchronization Algorithm},
booktitle = {9th ACM Symp.~on Principles of Distributed Computing},
month = aug,
year = {1990},
address = {Quebec City, Canada},
pages = {133--143},
field = {Connection management}
}
to be published lateron this year
> "A Statistical Clock Synchronization Algorithm for
> Anisotropic Networks"
> G. Florin, D. Couvet, S. Natkin, Centre D'Etude et
> De Recherche En Informatique, France
Ugo De Carlini
"A simple algorithm for CLock Synchronization in Transputer networks"
Software Practice and Experience
vo.18, #4, April 1988, p.331-347
Duda et al.
"Estimation of the global time in distributed systems"
Proceedings of the 7th Int'l Conference on Distr. Computing Systems
Berlin, Sept. 1987, p.299-306
--
***** ***** Manfred Pfluegl - believer of "Per Aspera Ad Astra"
* **** * **** pfluegl@uci.edu (Internet)
* ***** **** pfluegl@uci.bitnet (Bitnet)