🚀 go-pugleaf

In article <1992Sep3.123226.14205@hubcap.clemson.edu>, 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.

No such algorithm can exist, given some simple assumptions about A, B, and
the watchs - e.g., that only a fixed number of messages can be sent or can
arrive between successive ticks of a watch.

The proof is by contradiction.  We assume that SOME synchronization algorithm
exists.

Without loss of generality, we assume that A's watch initially reads 0;
B's watch might be set to anything.

Lemma:  An algorithm exists in which B has no watch.

Proof:  Suppose we wish to synchronize to watches (including a simulated watch
on B) to with delta seconds.  Every delta seconds on its watch, A sends a
"tick" message to B.  (If A wants to send B a message at exactly the same
time, it piggy-backs a "tick" message on it.)  Whenever B receives a "tick"
message, it increments a local counter.  Once AB seconds have gone by, B's
counter will be indistinguishable from a watch; it will have a maximum error
of delta just before the next "tick" arrives.  (The problem statement is vague
on what assumptions we can make about the timing resolution of the watches.
Clearly, the resolution must be at most delta.  If the algorithm requires a
finer resolution, A can send "tick" messages more often.)


Lemma:  An algorithm exists in which A sends the first message, and B sends
nothing until after it has received the first message.

Proof:  Clear, since nothing in the problem specification allows us to AVOID
this situation with certainty, and the algorithm must still work.  So we
simply require it.


Lemma:  An algorithm exists in which each machine responds to every message
it receives.  (In particular, this means that the receiver of a message can
always tell which of its own messages it was in response to, with no extra
information.)

Proof:  Clear, since we can always send extra messages (or piggyback respon-
ses onto messages to keep the total number between ticks down).


Lemma:  An algorithm exists in which every message from B to A consists only
of the value of B's watch.

Proof:  Consider the computation that B goes through to determine its message.
The only inputs are its initial state, all the messages it has already
received, and its local watch.  We can assume that A knows B's initial state,
since if there is any implementation, giving A more data can't break it; and A
certainly knows what messages it sent, and by the previous lemma, exactly
which ones B has seen before constructing this response.  Hence, given only
the value of B's watch, A can simulate B and reconstruct the message.


Lemma:  B doesn't even have to send the value of its watch!

Proof:  By the first lemma, B doesn't need a watch, only a counter of ticks
it has received.  If B ack's every tick, A will know exactly what B's counter
contains at the time it constructs any response message.

Lemma:  We can replace B by a machine that sends just an "ack" message in
immediate response to every message it receives from A.

Proof:  Clear.


But now consider the world from A's point of view.  It sends some messages,
and receives in response a series of indistinguishable ack's.  The only
thing that can vary is the interval from the moment A sends a message until
it receives that message's ack.  However, that interval depends only on the
round-trip time; it will be exactly the same in the cases AB=2, BA=0 and
AB=BA=1.  This information is insufficient for A to calculate the difference
between its watch value an B's.  As a result, the messages A sends out must
be the same in both situations.  This means B sees exactly the same messages
at exactly the same times in both cases, too.  So it can't distinguish these
two cases either.  Hence B doesn't can't reset its watch effectively either.

							-- Jerry