The effective coordinated activity of processors within a distributed system typically requires synchronization of their local clocks. This task is particularly challenging in sensornets, since the synchronization must be very precise and the power available for synchronization signals is severely limited.

We assume that each processor in a sensornet has a clock which is offset by an unknown amount from a universal time standard. In order to synchronize, two nodes must have an accurate estimate of the difference between their offsets. The core of any synchronization algorithm is a distributed method of achieving these estimates. The recent Reference-Broadcast Synchronization (RBS) design postulates that many synchronization signals are broadcast locally within the sensornet and received simultaneously by different sets of nodes. The nodes receiving a signal observe (with some error) the times of reception on their local clocks and share those observations among themselves.

Given a model of measurement error, we consider the problem of characterizing efficient estimators of the offsets, developing a distributed algorithm for computing these estimators, and choosing an optimal set of synchronization signals on which to base the estimation. In order to solve these problems we draw upon results from network flow theory, electric circuit theory, random walks on graphs, convex optimization, computational linear algebra and theoretical statistics.

This is joint work with Jeremy Elson, Deborah Estrin, Christos Papadimitriou and Scott Shenker.