Seminars at the Faculty of Informatics

The Faculty of Informatics is pleased to announce a seminar given by Dr. Fabian Kuhn
TITLE: Algorithmic Challenges in a Networked World
SPEAKER: Dr. Fabian Kuhn, post-doctoral researcher at MIT
DATE: April 29th, 2009
PLACE: USI Università della Svizzera italiana, room SI-008, Informatics building (Via G. Buffi 13)
TIME: 09.30

Over the last years, large-scale computer networks and distributed systems have become increasingly abundant and important. Driven by technological advances, new kinds of networks and applications have emerged. It can certainly be expected that this trend will continue. The computational and communication tasks that need to be solved in such a networked environment lead to a plethora of algorithmic challenges and problems. In my talk, I will present a selection of results on basic computations in various kinds of decentralized distributed systems. I will highlight common themes and focus on important techniques.
Typically, in a large decentralized network, no device can have a complete view of the whole network and every node needs to make decisions based on individual partial knowledge about the system. Nevertheless these decisions need to be consistent and the network as a whole has to achieve a global goal. At the example of basic graph-theoretic structures such as colorings and dominating sets, I will demonstrate that this leads to fundamental trade-offs between the quality of the solution and the amount of communication needed.
Further, many modern types of networks are inherently dynamic, demanding highly adaptive solutions. Novel networking paradigms such as wireless ad hoc and sensor networks also require new theoretical models that allow to develop efficient distributed algorithms. At a few examples, I will present possible techniques to cope with dynamic networks, wireless communication, and other basic challenges of distributed computing environments.
Fabian Kuhn earned his Ph.D. degree from ETH Zurich in 2005 for his work on locality phenomena in distributed algorithms. After finishing his Ph.D. thesis, which was awarded with the ETH medal, he joined Microsoft Research Silicon Valley. Following the research stay in California, Fabian returned to ETH Zurich for a year and afterwards joined the theory group at MIT in 2008. Fabian's research focuses on algorithms and combinatorics in general. In particular, he is interested in algorithmic work in the context of networks and distributed systems.

URL 1: