Speaker: Roger Wattenhofer ETH Zurich
Time: 2011-09-28 15:30-2011-09-28 16:30
Venue: FIT 1-222

Abstract:

In my talk we discuss the fundamentals of distributed algorithms, also known as message passing algorithms, or the "local" model. A distributed system is represented by a graph. We would like to solve classic combinatorial optimization problems by having the nodes of the graph just talk to their neighbors in the graph. As a running example throughout the talk we will use the so-called Maximal Independent Set (MIS) problem. Together, we figure out and discuss simple deterministic and randomized algorithms to solve the MIS problem in a distributed context. We will discuss applications of the MIS problem, such as coloring. Then we look at some of the state of the art results of the MIS problem and discuss the lower bound technique by Linial, the upper bound technique by Cole and Vishkin, and finally the lower bound by Kuhn et al. We will also have a quick look at related problems, and the most important open questions in this area.

Short Bio:

Roger Wattenhofer is a full professor at the Information Technology and Electrical Engineering Department, ETH Zurich, Switzerland. He received his doctorate in Computer Science in 1998 from ETH Zurich. From 1999 to 2001 he was in the USA, first at Brown University in Providence, RI, then at Microsoft Research in Redmond, WA. He then returned to ETH Zurich, originally as an assistant professor at the Computer Science Department. Roger Wattenhofer's research interests are a variety of algorithmic and systems aspects in computer science and information technology, currently in particular wireless networks, multi-core systems, peer-to-peer computing, and social networking. He publishes in different communities: distributed computing (e.g., PODC, SPAA, DISC), networking (e.g., MobiCom, MobiHoc, SenSys, IPSN, HotNets), or theory (e.g., STOC, FOCS, SODA, ICALP).