darrell@sdcsvax.UUCP (05/15/87)
I am looking for methods and algorithms to help keep accurate and synchronous time on a network of real-time microcomputers. The nodes of the net will be spread out in many different arrangements: 2-point, star, and ring. The nodes are required to act together on command (e.g. at 3:45:55 P.M. turn on your devices), even though they are hundreds of miles apart. All references and comments will be appreciated. teltone!warren -- (206) 827-9626 Warren Seltzer ...uw-beaver_____!tikal!warren Teltone Corporation .......fluke___/ P.O. Box 657 ...microsoft__/ Kirkland, WA 98033
ast@cs.vu.nl (Andy Tanenbaum) (05/17/87)
To get the time truly synchronized on a network of machines hundreds of miles apart, you might consider WWV. This is a radio station run by the U.S. Federal Government that broadcasts the time accurately to the microsecond range. Special receivers are available for it. If you really want to be picky, you should correct for the propagation time from the transmitter to the receiver, since radio waves only travel 1 foot per nanosecond. Another thing you might do is check with your local radio astronomers. They have been doing long-baseline interferometry for years, where long baseline in this case means roughly the diameter of the earth. This work requires very accurate time synchronization, and it is possible they have published papers on how they do it. Andy Tanenbaum (ast@cs.vu.nl) [ Hmm. How often would you sample the time? Isn't the time broadcast only ] [ every few seconds? What about clock drift between samples? --DL ]
bobg@aspen3.UUCP (Operator) (05/18/87)
Xerox has done substantial work in this area. I have in front of me: Maintainting the Time in A Distributed System An Example of a Loosely-Coupled Distributed Service Keith A Marzullo Xerox Office Systems Division I beleive they distribute these technical reports through their office at 3333 Coyote Hill Road, Palo Alto, CA 94304. I hope this helps. Bob Greiner Motorola Microcomputer Division Tempe, AZ 85282
jqj@gvax.cs.cornell.edu (J Q Johnson) (05/24/87)
A number of people at Cornell are doing active research in algorithms for distributed time synchronization. In addition to Keith Marzullo (now at Cornell, not Xerox) are Fred B. Schneider and Sam Toueg. You might be interested in looking at their recent papers.
howard@COS.COM (Howard C. Berkowitz) (06/05/87)
An approach used in performance measurement, developed jointly by the NBS Time Lab and AT&T Bell Labs, assumes an accurate time source at a central reference point (e.g., a dual oven crystal locked to WWV for 1**10-7 accuracy). In this approach, a slave node desiring synchronization contacts the master timer using a communications channel of constant delay. Dial calls through AT&T (unclear about others) have constant delay, on both sides of the call, during that call. The master transmits its current time value to the slave. On receiving and storing it, the slave retransmits its current time-of-day value to the master. The master computes the difference between its current time value and that sent to it, divides it by two (assuming equal delay on both sides of the channel), and sends that quotient as a correction factor to the slave. This process is repeated until the clocks synchronize. Failure to synchronize (within clock accuracy) suggests variable channel delay. I am not convinced we have a decent way to synchronize in a ring, although it can be approximated, in a deterministic network, by adding the delays through each node. I would not want to try on a CSMA LAN unless it were idled other than for timing traffic.
darrell@sdcsvax.UUCP (06/06/87)
>range. Special receivers are available for it. If you really want to be >picky, you should correct for the propagation time from the transmitter >to the receiver, since radio waves only travel 1 foot per nanosecond. > >Another thing you might do is check with your local radio astronomers. The last radio astromoner I talked to that did this synchronized 2 atomic clocks in the same room, and then picked one of them up and flew it across the country to be used as the time stamp for the data recorded by the other radio telescope. [ This illustrates a basic problem found in distributed systems and not in ] [ centralized systems. Keeping a globally consistent view of time is hard ] [ Those of us without atomic clocks have to rely on approximations, that's ] [ why all of the fancy protocols are needed. --DL ]