HartungGorre Verlag
Inh.: Dr.
Renate Gorre D78465
Konstanz Fon: +49 (0)7533 97227 Fax: +49 (0)7533 97228 www.hartunggorre.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 9783866283909
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:
HartungGorre Verlag / D78465
Konstanz / Germany
Telefon: +49
(0) 7533 97227 Telefax: +49 (0) 7533
97228
http://www.hartunggorre.de eMail: verlag@hartunggorre.de