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 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:
Series in Distributed Computing in

Direkt bestellen bei / to order directly from:

Hartung-Gorre Verlag

Hartung-Gorre Verlag / D-78465 Konstanz / Germany

Telefon: +49 (0) 7533 97227 Telefax: +49 (0) 7533 97228 eMail: