home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / comp / parallel / 2034 < prev    next >
Encoding:
Text File  |  1992-09-03  |  2.8 KB  |  67 lines
  1. Newsgroups: comp.parallel
  2. Path: sparky!uunet!destroyer!gatech!hubcap!fpst
  3. From: anik@crhc.uiuc.edu (Sadun Anik)
  4. Subject: Re: Synchonizing watches
  5. In-Reply-To: steve@hubcap.clemson.edu's message of 2 Sep 92 12:27:17 GMT
  6. Message-ID: <1992Sep3.172657.10929@hubcap.clemson.edu>
  7. Sender: fpst@hubcap.clemson.edu (Steve Stevenson)
  8. Nntp-Posting-Host: lyra.crhc.uiuc.edu
  9. Organization: Center for Reliable and High-Performance Computing
  10. References: <1992Sep3.123226.14205@hubcap.clemson.edu>
  11. Date: 3 Sep 92 11:14:31
  12. Approved: parallel@hubcap.clemson.edu
  13. Lines: 52
  14.  
  15. In article <1992Sep3.123226.14205@hubcap.clemson.edu> steve@hubcap.clemson.edu ("Steve" Stevenson) writes:
  16.    [I saw this on sci.logic. I thought it was a nice problem for this group.
  17.      steve]
  18.    >From: dougs@tvnews.tv.tek.com (Doug Stevens)
  19.    >Message-ID: <1992Sep1.234452.26917@tvnews.tv.tek.com>
  20.  
  21.    [....]
  22.  
  23.    A and B are two people at two ends of a very slow telephone connection. 
  24.    They are both completely cut off from the world except for their connection 
  25.    with each other.  In particular, they have no idea what time it is in the 
  26.    real world.
  27.  
  28.    There is a delay AB in the transmission of what is being said by
  29.    A to B, and a delay BA in the transmission of what is being said
  30.    by B to A. The delay AB does not equal the delay BA. The delays, for the
  31.    purpose of this problem, are on the order of minutes in each direction.
  32.  
  33.    Both A and B have watches. Before they begin to talk, the watches are not
  34.    set to the correct time, nor are they set to the same time.
  35.  
  36.    The problem is to devise a procedure such that A and B can, via their 
  37.    telephone connection only, accurately synchronize their watches (to
  38.    within a few seconds). The watches do not have to reflect time in the
  39.    real world, but must match each other. Both A and B will know the procedure 
  40.    before the call begins, and each will know whether he is A or B.
  41.  
  42.    Thanks for any help.
  43. ----------------
  44.  
  45. OK I'll bite. It is trivial for A and B to figure out AB+BA. It is
  46. also trivial for them to synchronize their watches assuming AB=BA (or
  47. any preset assumtion on AB/BA). At this point their watches are
  48. actually synchronized. You can not refute this with any communication
  49. between A and B using this communication channel. My wild guess :) and
  50. please tell me if this is wrong.
  51.  
  52. [I don't think that your assumptions are safe. Steve]
  53.  
  54.  
  55. If you are using a third person "C" to check if their watches are
  56. actually synchronized using delays AC,CA,BC and CB, then the system you
  57. are solving is perturbed so the previous solution doesn't need to be
  58. valid. But this is irrelevant because this is not the system  in the
  59. problem. The solution is not also valid if you have another means of
  60. communication between A and B. 
  61.  
  62. --
  63. Sadun Anik, U of Illinois at Urbana-Champaign
  64. Center for Reliable and High-performance Computing
  65. e-mail: anik@crhc.uiuc.edu
  66.  
  67.