Gradient Clock Synchronization

Date: Thursday, November 11, 2010
Speaker: Christoph Lenzen
Venue: TU Wien

In the clock synchronization problem, on seeks to keepdevices in a communication network as closely synchronized as possiblein face of drifting clocks and unknown message transmission times. Thisand similar tasks have been research topic for several decades now,both in theory and practice. So, what is different about this talk? Weask not only for the maximum worst-case clock skew between any twonodes in the system to be minimal, but also for devices which canestimate each other’s clock values accurately to be synchronizedtightly. For many applications, the latter property is crucial, as theymerely require that devices capable of direct communication arewell-synchronized. Moreover, we allow for arbitrary network dynamics,i.e., communication links may fail and become operative again atarbitrary times. Interestingly, this challenging task can be optimallysolved by a stunningly simple algorithm.

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

Short Bio: Christoph Lenzen studied mathematics at the university ofBonn and received his diploma degree in October 2007. Currently he isPh.D. student in the Distributed Computing Group at ETH Zurich and isgoing to graduate in December. His research topics cover distributedgraph algorithms, clock synchronization, and load balancing algorithms.The line of work on gradient clock synchronization has beenparticularly successful, with publications at FOCS, PODC, and in JACM,as well as the best paper award at PODC 2009.

Posted in RiSE Seminar