CLOCK SYNCHRONIZATION AND THE POWER OF BROADCASTING

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 epsilon, for some fixed constant epsilon. 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 + K/1)epsilon-on the precision of clock synchronization attainable for n greater-than-or-equal-to 3 process using K (n-1)-casts, 3 less-than-or-equal-to K less-than-or-equal-to n, (2) matching upper and lower bounds of (1 + n/1)epsilon-on the precision of clock synchronization attainable for n greater-than-or-equal-to 3 processes using an arbitrary number of (n-1)-casts, and (3) matching upper and lower bounds of (1 + n/n-2)epsilon-on the precision attainable using 2-casting.