🚀 go-pugleaf

In article <1992Sep3.123226.14205@hubcap.clemson.edu> (which I found in
comp.parallel) steve@hubcap.clemson.edu ("Steve" Stevenson) writes:
>[I saw this on sci.logic. I thought it was a nice problem for this group.
>  steve]
>>From: dougs@tvnews.tv.tek.com (Doug Stevens)
>>Message-ID: <1992Sep1.234452.26917@tvnews.tv.tek.com>
>
>[....]
>
>A and B are two people at two ends of a very slow telephone connection. 
>They are both completely cut off from the world except for their connection 
>with each other.  In particular, they have no idea what time it is in the 
>real world.
>
>There is a delay AB in the transmission of what is being said by
>A to B, and a delay BA in the transmission of what is being said
>by B to A. The delay AB does not equal the delay BA. The delays, for the
>purpose of this problem, are on the order of minutes in each direction.
>
>Both A and B have watches. Before they begin to talk, the watches are not
>set to the correct time, nor are they set to the same time.
>
>The problem is to devise a procedure such that A and B can, via their 
>telephone connection only, accurately synchronize their watches (to
>within a few seconds). The watches do not have to reflect time in the
>real world, but must match each other. Both A and B will know the procedure 
>before the call begins, and each will know whether he is A or B.
>
>Thanks for any help.
>

I have graduated on this subject just about a year ago. In my thesis I quote
a few papers (listed below) which introduce the problem and introduce some
solutions. These solutions were mainly useful in particular network 
topologies. I tried to combine and extend the given solutions and implement
it on a network of transputers. The results seemed very promising (less than
10% communication overhead, can be reduced; accurate clocks, synchronous at
about a few us).
At the moment further work is done by a graduate student who has just
started his project.

Our group submitted a paper to EuroMicro, last year June in Paris which was
presented at the conference.

references:
  Christian F., "Probabilistic clock synchronisation", Distributed
      Computing, 1989 Vol. 3, No. 3, pp. 146-158.
  Carlini, U. and U. Villano, "A Simple Algorithm for Clock Synchronisation
      in Transputer Networks", Software - Practice and Experience, April
      1988, pp. 331-347
  Halpern, J.Y.,  B. Simons, and H.R. Strong, "Decentralized
      synchronisation of clocks", U.S. Patent 4584643, April 22, 1986.
  Kopetz, H. and W Ochsenreiter, "CLock synchronisation in Distributed
      Real-Time Systems", IEEE Transactions on Computers, Vol C-36, No. 8,
      August 1987, pp. 933-940.
  Lamport, L. "Time, Clocks, and the Ordering of Events in a Distributed
      System", Comm. of the ACM, 1978, Vol. 21, No. 7, July, pp. 558-565.
  Lamport, L. and P.M. Melliar-Smith, "Synchronizing Clocks in the Presence
      of Faults", Journal of the ACM, 1985, VOl.32, No. 4, January, pp.
      52-78
  Vervoort, W.A., R. te West, A.L. Schoute and J. Hofstede, "Distributed 
      Time Management in Transputer Networks", in: Proc. of EuroMicro '91
      (IEEE Workshop on Real-Time Systems), Paris, France, 1991, pp.
      224-230.
  
I would greatly appreciate it if anyone knows of similar projects or
research done in the same field, he or she sends me a message containing
pointers to it.

----------------------------------------------------------------------------
Andre Hoekstra            Any nice things go here             artskeoH erdnA
Universiteit Twente               here                   etnewT tietisrevinU
Faculteit Informatica            or here               acitamrofnI teitlucaF
Room WB-Z122
P.O. Box 217,
NL-7500 AE Enschede
The Netherlands
+31 53 893296
ahoekstr@cs.utwente.nl--------------------------------ln.etnewtu.sc@rtskeoha