Hartung-Gorre Verlag Inh.: Dr. Renate Gorre D-78465 Konstanz Fon: +49 (0)7533 97227 Fax: +49 (0)7533 97228 www.hartung-gorre.de

S

Series in Distributed Computing
edited by Roger Wattenhofer
Vol. 14

Christoph Lenzen

Synchronization and Symmetry Breaking

in Distributed Systems

1^st edition/1. Aufl. 2011. X, 184 pages/Seiten, € 64,00.
ISBN 978-3-86628-390-9

An emerging characteristic of modern computer systems is that it is becoming ever more frequent that the amount of communication involved in a solution to a given problem is the determining cost factor. In other words, the convenient abstraction of a random access memory machine performing sequential operations does not adequately reflect reality anymore. Rather, a multitude of spatially separated agents cooperates in solving a problem, where at any time each individual agent has a limited view of the entire system's state. As a result, coordinating these agents' efforts in a way making best possible use of the system's resources becomes a fascinating and challenging task. This dissertation treats of several such coordination problems arising in distributed systems.

In the clock synchronization problem, devices carry clocks whose times should agree to the best possible degree. As these clocks are not perfect, the devices need to perpetually resynchronize by exchanging messages repeatedly. We give provably optimal solutions for two different varieties of this problem: gradient clock synchronization and clock synchronization in wireless networks.

Many load balancing tasks can be abstracted as distributing n balls as evenly as possible into n bins. In a distributed setting, we assume the balls and bins to act as independent entities that seek to coordinate at a minimal communication complexity. We show that under this constraint, a natural class of algorithms requires a small, asymptotically optimal number of communication rounds to achieve a constant maximum bin load.

Finally, we consider two basic combinatorial structures, maximal independent sets and dominating sets. For several families of graphs, we shed new light on the distributed complexity of computing dominating sets of approximatively minimal size or maximal independent sets, respectively.

About the author:

Christoph Lenzen received his diploma degree in mathematics from the University of Bonn, Germany, in 2007. Afterwards he joined the Distributed Computing Group at ETH Zurich. Supervised by Professor Roger Wattenhofer, his graduate studies took place from 2007 to 2010. He received his Ph.D. degree from ETH Zurich after defending his thesis in 2011.

Keywords: gradient clock synchronization, wireless networks, adaptive randomized load balancing, maximal independent set, minimum dominating set, restricted families of graphs, asymptotic bounds, competitive analysis

Series in Distributed Computing

Direkt bestellen bei / to order directly from:

Hartung-Gorre Verlag / D-78465 Konstanz / Germany

Telefon: +49 (0) 7533 97227 Telefax: +49 (0) 7533 97228
http://www.hartung-gorre.de eMail: verlag@hartung-gorre.de