**Series in Distributed
Computing
**

Christoph Lenzen

Synchronization and Symmetry Breaking

in Distributed Systems

1^{st} edition/1. Aufl. 2011, X, 184 pages/Seiten, € 64,00.

ISBN 3-86628-390-3 and 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 c*lock 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

Direkt
bestellen bei / to order directly from: Hartung.Gorre@t-online.de

Series in Distributed Computing in http://www.hartung-gorre.de

Direkt bestellen bei / to order directly from: Hartung.Gorre@t-online.de

**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**