home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / comp / parallel / 2047 < prev    next >
Encoding:
Internet Message Format  |  1992-09-03  |  4.3 KB
  1. Xref: sparky comp.parallel:2047 sci.logic:1343
  2. Newsgroups: comp.parallel,sci.logic
  3. Path: sparky!uunet!gatech!hubcap!fpst
  4. From: ahoekstr@cs.utwente.nl (Andre Hoekstra)
  5. Subject: Re: Synchonizing watches
  6. Message-ID: <1992Sep4.121432.18134@hubcap.clemson.edu>
  7. Apparently-To: comp-parallel@uunet.uu.net
  8. Keywords: clocks, synchronisation
  9. Sender: ahoekstr@cs.utwente.nl
  10. Nntp-Posting-Host: waal
  11. Organization: University of Twente, Dept. of Computer Science
  12. References: <1992Sep3.123226.14205@hubcap.clemson.edu>
  13. Date: Fri, 4 Sep 1992 10:22:16 GMT
  14. Approved: parallel@hubcap.clemson.edu
  15. Lines: 80
  16.  
  17. In article <1992Sep3.123226.14205@hubcap.clemson.edu> (which I found in
  18. comp.parallel) steve@hubcap.clemson.edu ("Steve" Stevenson) writes:
  19. >[I saw this on sci.logic. I thought it was a nice problem for this group.
  20. >  steve]
  21. >>From: dougs@tvnews.tv.tek.com (Doug Stevens)
  22. >>Message-ID: <1992Sep1.234452.26917@tvnews.tv.tek.com>
  23. >
  24. >[....]
  25. >
  26. >A and B are two people at two ends of a very slow telephone connection. 
  27. >They are both completely cut off from the world except for their connection 
  28. >with each other.  In particular, they have no idea what time it is in the 
  29. >real world.
  30. >
  31. >There is a delay AB in the transmission of what is being said by
  32. >A to B, and a delay BA in the transmission of what is being said
  33. >by B to A. The delay AB does not equal the delay BA. The delays, for the
  34. >purpose of this problem, are on the order of minutes in each direction.
  35. >
  36. >Both A and B have watches. Before they begin to talk, the watches are not
  37. >set to the correct time, nor are they set to the same time.
  38. >
  39. >The problem is to devise a procedure such that A and B can, via their 
  40. >telephone connection only, accurately synchronize their watches (to
  41. >within a few seconds). The watches do not have to reflect time in the
  42. >real world, but must match each other. Both A and B will know the procedure 
  43. >before the call begins, and each will know whether he is A or B.
  44. >
  45. >Thanks for any help.
  46. >
  47.  
  48. I have graduated on this subject just about a year ago. In my thesis I quote
  49. a few papers (listed below) which introduce the problem and introduce some
  50. solutions. These solutions were mainly useful in particular network 
  51. topologies. I tried to combine and extend the given solutions and implement
  52. it on a network of transputers. The results seemed very promising (less than
  53. 10% communication overhead, can be reduced; accurate clocks, synchronous at
  54. about a few us).
  55. At the moment further work is done by a graduate student who has just
  56. started his project.
  57.  
  58. Our group submitted a paper to EuroMicro, last year June in Paris which was
  59. presented at the conference.
  60.  
  61. references:
  62.   Christian F., "Probabilistic clock synchronisation", Distributed
  63.       Computing, 1989 Vol. 3, No. 3, pp. 146-158.
  64.   Carlini, U. and U. Villano, "A Simple Algorithm for Clock Synchronisation
  65.       in Transputer Networks", Software - Practice and Experience, April
  66.       1988, pp. 331-347
  67.   Halpern, J.Y.,  B. Simons, and H.R. Strong, "Decentralized
  68.       synchronisation of clocks", U.S. Patent 4584643, April 22, 1986.
  69.   Kopetz, H. and W Ochsenreiter, "CLock synchronisation in Distributed
  70.       Real-Time Systems", IEEE Transactions on Computers, Vol C-36, No. 8,
  71.       August 1987, pp. 933-940.
  72.   Lamport, L. "Time, Clocks, and the Ordering of Events in a Distributed
  73.       System", Comm. of the ACM, 1978, Vol. 21, No. 7, July, pp. 558-565.
  74.   Lamport, L. and P.M. Melliar-Smith, "Synchronizing Clocks in the Presence
  75.       of Faults", Journal of the ACM, 1985, VOl.32, No. 4, January, pp.
  76.       52-78
  77.   Vervoort, W.A., R. te West, A.L. Schoute and J. Hofstede, "Distributed 
  78.       Time Management in Transputer Networks", in: Proc. of EuroMicro '91
  79.       (IEEE Workshop on Real-Time Systems), Paris, France, 1991, pp.
  80.       224-230.
  81.   
  82. I would greatly appreciate it if anyone knows of similar projects or
  83. research done in the same field, he or she sends me a message containing
  84. pointers to it.
  85.  
  86. ----------------------------------------------------------------------------
  87. Andre Hoekstra            Any nice things go here             artskeoH erdnA
  88. Universiteit Twente               here                   etnewT tietisrevinU
  89. Faculteit Informatica            or here               acitamrofnI teitlucaF
  90. Room WB-Z122
  91. P.O. Box 217,
  92. NL-7500 AE Enschede
  93. The Netherlands
  94. +31 53 893296
  95. ahoekstr@cs.utwente.nl--------------------------------ln.etnewtu.sc@rtskeoha
  96.  
  97.