Clock synchronization and the power of broadcasting

Summary We investigate the power of a broadcast mechanism in a distributed network. We do so by considering the problem of synchronizing clocks in an errorfree 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 , for some fixed constant . 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) on the precision of clock synchronization attainable forn3 process usingK (n–1)-casts, 3Kn, (2) matching upper and lower bounds of (1+1/n) on the precision of clock synchronization attainable forn3 processes using an arbitrary number of (n–1)-casts, and (3) matching upper and lower bounds of (1+n–2/n) on the precision attainable using 2-casting.Joseph Y. Halpern received a B.Sc. in mathematics from the University of Toronto in 1975, and a Ph.D. in mathematics from Harvard University in 1981. In between, he spent two years as the head of the Mathematics Department at Bawku Secondary School in Ghara. After a year as a visiting scientist at MIT, he joined IBM in 1982, where he is currently a research staff member, as well as being a consulting professor at Stanford University. He was manager of the mathematics and related computer sience department at IBM from 1987–1989. He was program chairman and organizer of the first conference on Theoretical Aspects of Reasoning About Knowledge in 1986, program chairman of the 1986 ACM Symposium on Principles of Distributed Computing and of the 1991 ACM Symposium on Theory of Computing. He was recipent (together with Ron Fagin) of the MIT Publisher's Prize for best paper at the 1985 International Joint Conference on Artificial Intelligence and again winner of the Publisher's Prize at the 1989 International Joint Conference on Artificial Intelligence.Ichiro Suzuki is an Associate Professor of Computer Science at the University of Wisconsin-Milwaukee. He received a D.E. degree in information and computer sciences from Osaka University, Japan, in 1983. His major research interests are distributed systems and computational geometry.This author was supported in part by the National Science Foundation under grant CCR-9004346