September 6th – September 11th 2009, Dagstuhl Seminar 09371
Algorithmic Methods for Distributed Cooperative Systems
For support, please contact
A standard scientific method for understanding complicated situations is to analyze them in a top-down, hierarchical manner. This approach also works well for organizing a large variety of structures; that is why a similar hierarchical, centralized approach has worked extremely well for employing computers in so many aspects of our life: data is gathered, processed, and the result is administered by one central authority.
On the other hand, the structures in our modern world are getting increasingly complex. The resulting challenges have become so demanding that it is impossible to ignore that a large variety of systems are based on a very different principle: the stability and effectiveness of our modern political, social and economic structures relies on the fact that they are based on decentralized, distributed and self-organizing mechanisms. This paradigm shift is also reflected in a variety of modern computing systems, which work in a distributed manner, based on local (and thus: incomplete) information and interaction, and implement the results in a localized fashion; as opposed to a variety of social or economic situations, we may assume that the individual components of such a system are not primarily selfish, but pursue a joint goal that is to be reached in collaboration.
The purpose of this seminar was to bring together researchers from different disciplines whose central interest is in both algorithmic foundations and application scenarios of distributed cooperative systems. In particular, participants from the following communities were present:
- Algorithmic Foundations.
- When developing a systematic method for solving an algorithmic problem by a cooperating set of loosely coupled processors, the result is a distributed algorithm. One of the resulting consequences is incomplete information, for which an increasing number of algorithmic aspects have been studied. Moreover, a number of additional issues are considered, such as communication complexity, timing issues, and the amount and type of information that is available to individual processors.
- Sensor networks.
- In recent time, the study of wireless sensor networks (WSN) has become a rapidly developing research area, both from the theoretical and the practical side. Typical scenarios involve a large swarm of small and inexpensive processor nodes, each with limited computing and communication resources, that are distributed in some geometric region; communication is performed by wireless radio with limited range. From an algorithmic point of view, these characteristics imply absence of a central control unit, limited capabilities of nodes, and limited communication between nodes. This requires developing new algorithmic ideas that combine methods of distributed computing and network protocols with traditional centralized network algorithms. In other words: How can we use a limited amount of strictly local information in order to achieve distributed knowledge of global network properties? Just now, an important set of additional challenges for sensor networks is starting to emerge from mobile nodes, making it necessary to deal with additional problems arising from network dynamics.
- Multi-Robot Systems
- Multi-robot systems consist of several individual robots, either identical or heterogeneous. Among the scenarios for teams or swarms of autonomous robots are robot soccer (RoboCup), rescue missions, exploration and other complex tasks that can be carried out in a distributed fashion. Beyond the technical aspects of perception, behaviors, learning, and action, the most interesting issue in the context of this interdisciplinary seminar are various modeling aspects that are getting quite close to those faced in areas such as SN: after all, a sensor-equipped robot becomes quite similar to a mobile sensor node, and both face similar difficulties, but also possibilities.
- Application scenarios.
- In order to provide further scenarios for challenges and discussions, we plan to include a selection of researchers from other application areas; these include
- Traffic: making use of car-to-car communication, it has become possible to provide online, up-to-date local information and coordination. What challenges can be tackled by making use of these possibilities?
- Biology: swarm behavior of animals has developed over millions of years. What lessons can be learned from such behavior?
These four aspects were subdivided into algorithmic foundations (provided by AF), two specific areas (SN and RT) that form the link between pure theory and real-life applications, and a variety of real-life challenges (provided by AP) that can serve as goals and benchmarks for the other scientific work. Quite naturally, there was some amount of overlap between these four areas in terms of individual researchers, as various scientists combine theory and practice, to a varying degree. Despite of the previous distinction between the different fields, a variety of aspects implied that similar problems were faced, so that a dialogue between the researchers turned out to be quite fruitful.
The seminar brought together 35 researchers from nine countries. The 20 presentations, varying in length, covered a large variety of topics. Owing to the combination of different research areas, there were a number of survey talks and discussion session, but also a variety of individual research presentations. In addition, there was sufficient time for informal discussion and small-scale interaction. Overall, participants agreed that the interdisciplinary nature of the seminar was quite fruitful. There was strong interest in repeating this event with a similar combination of fields and researchers in the not-too-distant future.
- Artificial Intelligence
- Data Structures
- Cooperative systems
- Sensor networks