| Clock Synchronization and the Power of Broadcasting (1996) | |||||||||||||||
Abstract | |||||||||||||||
| : We investigate the power of a broadcast mechanism in a distributed network. We do so by considering the problem of synchronizing clocks in an error-free network, under the assumption that there is no upper bound on message transmission time, but that broadcast messages are guaranteed to be received within an interval of size ffl, for some fixed constant ffl. This is intended to be an idealization of what happens in multiple access networks, such as the Ethernet. We then consider tradeoffs between the type and number of broadcasts, and the tightness of synchronization. Our results include (1) matching upper and lower bounds of (1 + 1 K )ffl on the precision of clock synchronization attainable for n 3 processes using K (n \Gamma 1)-casts, 3 K n, (2) matching upper and lower bounds of (1 + 1 n )ffl on the precision of clock synchronization attainable for n 3 processes using an arbitrary number of (n \Gamma 1)-casts, and (3) matching upper and lower bounds of (1 + n\Gamma2 n ... | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||