Informatics, TU Vienna

Optimal Gradient Clock Synchronization in Dynamic Networks

In the clock synchronization problem, on seeks to keep devices in a communication network as closely synchronized as possible in face of drifting clocks and unknown message transmission times.

Abstract

In the clock synchronization problem, on seeks to keep devices in a communication network as closely synchronized as possible in face of drifting clocks and unknown message transmission times. This and similar tasks have been research topic for several decades now, both in theory and practice. So, what is different about this talk? We ask not only for the maximum worst-case clock skew between any two nodes in the system to be minimal, but also for devices which can estimate each other's clock values accurately to be synchronized tightly. For many applications, the latter property is crucial, as they merely require that devices capable of direct communication are well-synchronized. Moreover, we allow for arbitrary network dynamics, i.e., communication links may fail and become operative again at arbitrary times. Interestingly, this challenging task can be optimally solved by a stunningly simple algorithm.

The talk will comprise two parts. First, we present the problem and our results to a general audience. In the second, more technical part, we try to shed light on the techniques by which we obtain our asymptotically optimal bounds.
 

Biography

Christoph Lenzen studied mathematics at the university of Bonn and received his diploma degree in October 2007. Currently he is Ph.D. student in the Distributed Computing Group at ETH Zurich and is going to graduate in December. His research topics cover distributed graph algorithms, clock synchronization, and load balancing algorithms. The line of work on gradient clock synchronization has been particularly successful, with publications at FOCS, PODC, and in JACM, as well as the best paper award at PODC 2009.