Series in Distributed Computing
In a distributed computation, many autonomous processors intend to jointly come up with a solution for a given problem. It is usually assumed that the processors are located at different sites and are connected to each other by a network. Coordination between different processors (also called network nodes) is done by exchanging messages. If the input for a given problem is distributed among the nodes of the network, nodes need to communicate in order to learn about each other's input.
In k units of time, it is only possible to send information to nodes at distance at most k in the network. If the diameter of a given network is large, no node can learn about the whole network. In a few time units, a node can only gather data from nearby nodes. Thus, all nodes have to base their computations on partial information. Nevertheless, all network nodes together have to reach a common solution for the problem at hand. Achieving a global goal based on local information is therefore one of the most fundamental problems in the area of distributed computing.
This thesis considers the complexity of different important distributed coordination tasks. In particular, three major problems are discussed. First, we establish nearly tight upper and lower bounds on the possible trade-offs between running time and quality of the solution for a class of problems called covering and packing problems. Prominent network-related members of this problem class are for example minimum dominating set and maximum matching. Second, we consider protocols for coloring the nodes of the network. We analyze the potential of the simplest coloring algorithms where each node decides on a color based on the colors or identifiers of its direct neighbors only. Third, we study the distributed complexity of problems on a special kind of network topologies occurring in the context of wireless networks such as ad hoc or sensor networks.
About the author:
Fabian Kuhn received his M.Sc. degree in computer science (Dipl. Informatik-Ing ETH) from the Swiss Federal Institute of Technology (ETH), Zurich, Switzerland in 2001. In January 2002 he joined the Distributed Computing Group of Professor Roger Wattenhofer at ETH Zurich as a Ph.D. student and research assistant. In 2005 he earned his Ph.D. degree for his work on locality phenomena in distributed algorithms.
Keywords: locality, distributed algorithms, dominating sets, maximal independent sets, coloring, linear programming
Direkt bestellen bei / to order directly from:
Hartung.Gorre@t-online.de