Seminars at the Faculty of Informatics

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)
TIME: 10.30
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

URL 1: