Data Aggregation in Directed Networks

The Faculty of Informatics is pleased to announce a seminar given by Fabian Kuhn

DATE: Thursday, September 13th, 2012
PLACE: USI Università della Svizzera italiana, room SI-006, Informatics building (Via G. Buffi 13)
TIME: 14.30

ABSTRACT:
We consider basic data aggregation problems such as computing the minimum, the sum, or the average of a bunch of values distributed over a network. In standard, undirected networks, these tasks are well studied and can be solved by simple distributed algorithms in time proportional to the diameter of the network. In my talk, I will discuss the complexity of such fundamental aggregation problems in networks with unidirectional links. In the absence of reliable bidirectional links, the distributed computation of simple functions becomes a challenging task. We show that even in directed networks of diameter 2, computing any of the above functions requires at least

Omega(sqrt(n/B)) rounds if B bits can be transmitted in a single message. Up to logarithmic factors, this bound is tight.

BIO:
Fabian Kuhn is a full professor at the University of Freiburg, Germany and an adjunct professor at the USI Università della Svizzera italiana. He obtained his PhD from ETH Zurich in 2005. After the dissertation, Fabian Kuhn spent his postdoctoral years at Microsoft Research Silicon Valley, at ETH Zurich, and at MIT. In 2009, he joined the USI Università della Svizzera italiana in Switzerland as an assistant professor. Fabian Kuhn moved to Freiburg in spring 2012.