Distributed Computing

The general goal of our research in this field is to understand the algorithmic foundations and principles of distributed systems. To this end, the first task is to identify the key problems in this area and abstract away the technical issues related to a practical implementation – most notably ad-hoc sensor networks.

There is a clear feature shared by many distributed algorithms for ad-hoc sensor networks: they employ some basic subroutines that, more often than not, aim to solve classical graph-theoretical problems, such as finding a Maximal Independent Set or a Spanning Tree of the network. For instance, if a Maximal Independent Set or a Coloring with few colors of a network are known, then the operation in the network can be scheduled in such a way that no two neighboring nodes operate in parallel, which, in turn, prevents conflicts. Consequently it is of primary importance to understand how difficult graph-theoretical problems in a distributed setting are in order to be able to fully capture the principles behind the organization and the operation of wireless ad hoc networks.