Series in Distributed Computing
edited by Roger Wattenhofer
Vol. 8
Thomas Locher,
Foundations of
Aggregation and
Synchronization
in Distributed
Systems
1st
edition/1. Aufl. 2009, X, 134 pages/Seiten, € 64,00.
ISBN 978-3-86628-254-4
A distributed
system consists of several autonomous devices that are capable of performing
certain (computational) tasks and that have a means to communicate with each
other. A computer network system, such as the Internet, is a prototypical
example of a distributed system. While a distributed system has many advantages
over a single computational unit, e.g., the combined computational power of all
entities of a distributed system typically exceeds the power of any single
computational device considerably, the decentralized nature of distributed
systems also poses significant challenges.
In this thesis, two fundamental problems of distributed systems are studied.
The first part of this thesis focuses on the problem of computing global
functions that depend on the state of all devices in the system. Since each
device stores only a small part of the state of the entire system, interaction
between the devices is required in order compute such functions. If the
bandwidth of the communication channels is bounded, it may not be an efficient
solution to simply encode the state of each entity and forward this information
to a single participant in the system, which could then compute the result of
the function locally. Instead, the devices may attempt to aggregate the data
received from other devices in the system and use this information to compute
partial solutions of the global function. Such aggregation techniques may
greatly reduce the bandwidth consumption when computing global functions in a
distributed manner. The goal is to gain a deeper understanding of the
complexity of computing global functions using in-network aggregation.
In the second part of this thesis, we consider the problem that several
distributed applications and protocols require that all computational devices
maintain a common notion of time, but the devices do not have access to a
global timer. If each device possesses its own clock, the different clock rates
of these clocks necessitate the use of a clock synchronization algorithm whose
purpose is to compensate for the clock drifts by exchanging timing information
and adjusting the clock values according to the received information.
Synchronizing clocks is a challenging task mainly due to the uncontrollable and
potentially varying message delays, which render it impossible for the devices
to determine how accurate the timing information is that they receive from
other devices. The objective is thus to analyze the feasible degree of
synchronization, which not only depends on the message delays and the clock
drift rates, but also on other
parameters such as the frequency of communication.
About
the author:
Thomas Locher received his M.Sc.
degree in computer science from ETH Zurich, Zurich, Switzerland in 2005. In
2006 he joined the Distributed Computing Group of Professor Roger Wattenhofer
at ETH Zurich as a Ph.D. student and research assistant. In 2009 he earned his
Ph.D. degree for his work on aggregation and synchronization algorithms in
distributed systems.
Keywords: Distributed algorithms, distributed computing,
aggregation, holistic aggregate functions, clock synchronization, clock skew
minimization
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