Richard Karp (University of California, Berkeley):
Global Synchronization in Sensornets
Time synchronization in sensornets is a problem that combines stringent
precision requirements with severe resource constraints. We describe the
basic synchromnization model that underlies the recent
Reference-Broadcast-Synchronization proposal. We characterize the optimally
precise clock synchronization achievable within this model and
establish its global consistency. In the course of this analysis we point out
unexpected connections between optimal clock synchronization, random walks
and resistive networks. We sketch a polynomial-time algorithm for finding a
schedule of data acquisition giving the optimal trade-off between energy
consumption and precision of clock synchronization. As a byproduct of the
analysis we present an approximation scheme for computing the effective
resistance of an electric network. This is joint work with Jeremy Elson,
Christos Papadimitriou and Scott Shenker.