Title: Global solutions based on local information (slides in PDF)
Fabian Kuhn (University of Freiburg, Germany)
http://ac.informatik.uni-freiburg.de/kuhn
Abstract: Many of today's and future computer systems are large, decentralized networks in which each node can only directly communicate with a small number of other nodes. Communicating with a distant node typically requires time proportional to the distance. If something has to be computed in a fixed amount of time, each node has to compute its output based on information only from some local neighborhood. This raises the natural question of whether and to what extent local information is sufficient to solve tasks.
The research on local, distributed algorithms started in the mid 80ies in particular with a seminal paper on distributed coloring by Linial. The area has been very active in its beginning and with the increasing abundance of large-scale, decentralized systems, it has again received a boost in recent years. In my talk I will survey our current knowledge about local computations, I will present some selected important techniques and results, and we will discuss current challenges and potentially interesting directions for future research.
