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. Show more
External linksSearch via SFX
Organisational unit03604 - Wattenhofer, Roger / Wattenhofer, Roger
NotesInvited lecture on 11 November 2010.
MoreShow all metadata