Abstract
While the synchronization of time-of-day clocks ordinarily requires information flow in both directions between the clocks, this information need not flow directly via messages. However, to take advantage of indirect information flow, we have to make a number of complex assumptions about the behavior of the communication medium. To facilitate the verification of such assumptions, we develop a relativistic theory of observable clock synchronization that does not use or depend on a Newtonian framework or real time. Within the context of this theory, we focus on the problem of estimating the time on a remote clock. We generalize the concept of rapport to capture the situation when such an estimate is sufficient for clock synchronization purposes. With a single property, called the Observable Drift Property, we characterize the information flow required for obtaining rapport. We compare our relativized and observable concepts with analogs based on the notion of real time in order to show that we are studying the right quantities. We then give several clock synchronization algorithms that replace round trip synchronization algorithms but use only passive message receipt in a broadcast medium. These algorithms make the message cost of synchronization independent of the number of participants. Each algorithm measures and can report its own precision and does not depend on any assumed bound on message transmission and processing time. These properties have in the past only been associated with variants of round trip synchronization where the message cost is proportional to the number of participants. Verifying that a particular network can support one of these algorithms is reduced (by our results) to verifying four straightforward axioms and the Observable Drift Property.