Informatics Seminar on Friday, June 5th at 10.30 - Christoph Lenzen
Staff - Faculty of Informatics
Start date: 5 June 2009
End date: 6 June 2009
The Faculty of Informatics is pleased to announce a seminar given by Christoph Lenzen
TITLE: Clock Synchronization
SPEAKER: Christoph Lenzen, Distributed Computing Group, ETH Zuerich
DATE: Friday, June 5th, 2009
PLACE: USI Università della Svizzera italiana, room SI-008, Informatics building (Via G. Buffi 13)
The problem of achieving a common notion of time in a distributed system is well-known and well-studied. Many theoretical and practical works have been dedicated to the understanding of the degree to which time can be synchronized in face of drifting clocks, non-deterministic transmission delays, and multi-hop communication. Until a few years ago, however, not much attention has been spent to the question how close clock values of devices capable of direct communication can agree depending on the network diameter D.
This changed when an astonishing lower bound of log D / log log D was published, proving the intuition wrong that the synchronization quality of close devices solely depends on the message jitter. Even worse, straightforward algorithms fail to achieve even sublinear guarantees. After an introduction to the topic, this talk will give an overview of the results on the formulated gradient clock synchronization problem. The presented lower bound is matched by a surprisingly simple and elegant local algorithm. No initial knowledge on the topic is required of the audience.
Christoph Lenzen is PhD student in the Distributed Computing Group at ETH Zuerich. He earned a diploma degree in mathematics at the University of Bonn.
HOST: Prof. Rolf Krause