TOP
Search the Dagstuhl Website
Looking for information on the websites of the individual seminars? - Then please:
Not found what you are looking for? - Some of our services have separate websites, each with its own search option. Please check the following list:
Schloss Dagstuhl - LZI - Logo
Schloss Dagstuhl Services
Seminars
Within this website:
External resources:
  • DOOR (for registering your stay at Dagstuhl)
  • DOSA (for proposing future Dagstuhl Seminars or Dagstuhl Perspectives Workshops)
Publishing
Within this website:
External resources:
dblp
Within this website:
External resources:
  • the dblp Computer Science Bibliography


Dagstuhl Seminar 09371

Algorithmic Methods for Distributed Cooperative Systems

( Sep 06 – Sep 11, 2009 )


Permalink
Please use the following short url to reference this page: https://www.dagstuhl.de/09371

Organizers

Contact


Summary

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.


Participants
  • Nancy Amato (Texas A&M University, US) [dblp]
  • Tetsuo Asano (JAIST - Ishikawa, JP) [dblp]
  • Sven Behnke (Universität Bonn, DE) [dblp]
  • Ioannis Chatzigiannakis (RACTI - Rion, GR) [dblp]
  • Bastian Degener (Universität Paderborn, DE)
  • Alon Efrat (University of Arizona - Tucson, US) [dblp]
  • Sándor Fekete (TU Braunschweig, DE) [dblp]
  • Stefan Fischer (Universität Lübeck, DE) [dblp]
  • Thomas Gabel (Universität Freiburg, DE)
  • Jie Gao (Stony Brook University, US) [dblp]
  • Leszek A. Gasieniec (University of Liverpool, GB)
  • Deborah M. Gordon (Stanford University, US)
  • Riko Jacob (TU München, DE) [dblp]
  • Tom Kamphans (TU Braunschweig, DE)
  • Barbara Kempkes (Universität Paderborn, DE)
  • Alexander Kleiner (Universität Freiburg, DE)
  • Sebastian Kniesburges (Universität Paderborn, DE)
  • Alexander Kröller (TU Braunschweig, DE)
  • Alejandro Lopez-Ortiz (University of Waterloo, CA) [dblp]
  • Friedhelm Meyer auf der Heide (Universität Paderborn, DE) [dblp]
  • Ingrid Moerman (Ghent University, BE)
  • Bernhard Nebel (Universität Freiburg, DE) [dblp]
  • Andreas Nüchter (Jacobs University - Bremen, DE)
  • Dennis Pfisterer (Universität Lübeck, DE)
  • Tomasz Radzik (King's College London, GB)
  • Martin Riedmiller (Universität Freiburg, DE) [dblp]
  • Kay Römer (Universität Lübeck, DE) [dblp]
  • Paolo Santi (CNR - Pisa, IT)
  • Christian Scheideler (University of Paderborn, DE) [dblp]
  • Christiane Schmidt (TU Braunschweig, DE) [dblp]
  • Subhash Suri (University of California - Santa Barbara, US) [dblp]
  • Dirk Timmermann (Universität Rostock, DE) [dblp]
  • Roger Wattenhofer (ETH Zürich, CH) [dblp]
  • Peter Widmayer (ETH Zürich, CH) [dblp]
  • Katharina A. Zweig (Universität Heidelberg, DE) [dblp]

Classification
  • artificial intelligence
  • robotics
  • data structures
  • algorithms
  • complexity

Keywords
  • algorithms
  • cooperative systems
  • robotics
  • sensor networks