2010/10/06 by Leonid Barenboim, Barenboim, Leonid, Shlomi Dolev +3
Computer Science · #Distributed #FOS: Computer and information sciences #Parallel #and Cluster Computing (cs.DC) #cs.DC
paper · pdf · doi:10.48550/arxiv.1010.1112
arxiv created 2010/10/06 · arxiv updated 2015/03/17
We consider the problem of clock synchronization in a wireless setting where processors must power-down their radios in order to save energy. Energy efficiency is a central goal in wireless networks, especially if energy resources are severely limited. In the current setting, the problem is to synchronize clocks of m processors that wake up in arbitrary time points, such that the maximum difference between wake up times is bounded by a positive integer n, where time intervals are appropriately discretized. Currently, the best-known results for synchronization for single-hop networks of m processors is a randomized algorithm due to \citeBKO09 of O(√ n /m ⋅ poly-log(n)) awake times per processor and a lower bound of Omega(√(n/m)) of the number of awake times needed per processor \citeBKO09. The main open question left in their work is to close the poly-log gap between the upper and the lower bound and to de-randomize their probabilistic construction and eliminate error probability. This is exactly what we do in this paper. That is, we show a deterministic algorithm with radio use of Theta(√ n /m) that never fails. We stress that our upper bound exactly matches the lower bound proven in \citeBKO09, up to a small multiplicative constant. Therefore, our algorithm is optimal in terms of energy efficiency and completely resolves a long sequence of works in this area. In order to achieve these results we devise a novel adaptive technique that determines the times when devices power their radios on and off. In addition, we prove several lower bounds on the energy efficiency of algorithms for multi-hop networks. Specifically, we show that any algorithm for multi-hop networks must have radio use of Omega(√ n) per processor.