**Series in Distributed
Computing
**

**Thomas Locher,
**

Foundations of

Aggregation and Synchronization

in Distributed Systems

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

ISBN 3-86628-254-0 and 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**