🚀 go-pugleaf

dougs@tvnews.tv.tek.com (Doug Stevens) writes:

>------
>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.

I posted this problem to my news group, comp.parallel. Here are two
solutions I've received. The first gives a solution and the second
gives a Thinking Machines Corporation publication which deals with the 
problem

=========================== MODERATOR ==============================
Steve Stevenson                            fpst@hubcap.clemson.edu
Administrative address                     steve@hubcap.clemson.edu
Department of Computer Science,            comp.parallel
Clemson University, Clemson, SC 29634-1906 (803)656-5880.mabell
====================================================================

Date: Thu, 3 Sep 92 11:30:41 -0400
From: Clark VERBRUGGE <clump@asparagus.cs.mcgill.ca>
Message-Id: <9209031530.AA01758@asparagus.cs.mcgill.ca>
----------------------------------------------------------------------------
- A Solution -
----------------------------------------------------------------------------
Let the local time of A be tA, and the local time of B be tB.
Further, let tAB be the lag between messages going from A to B,
and let tBA be the symmetric value. Since both time pieces
are presumable ticking at the same rate, let tB = tA + C for some
constant C. If we can determine C, then they can synchronize their
watches.

1) A asks B the time. As s/he does, s/he notes how long it
   takes to hear the response from B. If B answers promptly, 
   A will now know 3 things:
      (tA)                 (local time)
      (tAB + tBA)          (total delay)
      (tA + C + tAB)       (time told to A by B)

2) A subtracts the last value from the first two:
      (tA) + (tAB + tBA) - (tA + C + tAB) = (tBA - C)

3) B now asks A the time. A hears the request at time
   tA', notes this time and responds. B now knows:
      (tA' + tBA)          (time told to B by A)

4) B tells A the value of (tA' + tBA). A can now calculate:
      (tA') + (tBA - C) - (tA' + tBA) = -C

5) A adds -C to his/her watch. Now both watches are in synch.

Of course this algorithm can only be as accurate as the
reaction time of the participants. It also assumes
that tAB and tBA are constant.

Clark Verbrugge
clump@binkley.cs.mcgill.ca

====================================================================
From: Barry Margolin <barmar@Think.COM>
	
Take a look at the algorithms in the Network Time Protocol, RFC 1305.  Or
if the specific algorithms aren't a good match, the references (there are
about 60 of them) at the end of the document should be useful.

-- 
Barry Margolin
System Manager, Thinking Machines Corp.

barmar@think.com          {uunet,harvard}!think!barmar

In article <1992Sep3.172632.10776@hubcap.clemson.edu> fpst@hubcap.clemson.edu (Steve Stevenson) writes:

>I posted this problem to my news group, comp.parallel. Here are two
>solutions I've received.  ...

>----------------------------------------------------------------------------
>- A Solution -
>----------------------------------------------------------------------------
>Let the local time of A be tA, and the local time of B be tB.
>Further, let tAB be the lag between messages going from A to B,
>and let tBA be the symmetric value. Since both time pieces
>are presumable ticking at the same rate, let tB = tA + C for some
>constant C. If we can determine C, then they can synchronize their
>watches.
>
>1) A asks B the time. As s/he does, s/he notes how long it
>   takes to hear the response from B. If B answers promptly, 
>   A will now know 3 things:
>      (tA)                 (local time)
>      (tAB + tBA)          (total delay)
>      (tA + C + tAB)       (time told to A by B)

TRUE

>2) A subtracts the last value from the first two:
>      (tA) + (tAB + tBA) - (tA + C + tAB) = (tBA - C)

TRUE

>3) B now asks A the time. A hears the request at time
>   tA', notes this time and responds. B now knows:
>      (tA' + tBA)          (time told to B by A)

NO.  A tells B  tA' only, not tA' + tBA.

The  synchroniztation problem can not be solved.  It's easy to see that A and 
B can synchronize their watches in the sense that whenever A sends a message,
A will know what time B will think it is when B receives the message, and
for every message A receives, A will know what time B thought it was when
B sent it, and vice-versa, but  that's as close as they can come to having
synchronized watches.

They can NOT synchronize their watches in the sense that a third person who
is in instant communication with each of them will see that A's watch and
B's watch read the same.



David Petry