Algorithmic Methods for Distributed Cooperative Systems

Motivation

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 workshop is to bring together researchers from different disciplines whose central interest is in both algorithmic foundations and application scenarios of distributed cooperative systems. In particular, we aim at the following communities:

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 a an increasing number of algorithmic aspects have been studied. Moreover, a number of additional issues have to be considered, such as communication complexity, timing issues, and the amount and type of information that is available to individual processors. Over the last years, the theory of distributed algorithms has seen a rapid development, leading to a vibrant research community; however, there is a number of important distinctions from what we have in mind: historically, distributed computing has looked at highly structured communication networks, such as mesh or butterfly architectures; in this seminar, we want to focus on mobile objects, rather than stationary nodes; and finally, previous work on distributed computing has focused on distributed computing for which the data itself is exogenous to the system, which differs from mobile robots or sensor systems that acquire data intentionally for a task.

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?
• Economics: distributed mechanisms are at the foundation of most aspects of our modern industrial world. What challenges and opportunities are to be faced by autonomous agents, and what distributed mechanisms would be useful for an economic society?
• Physics: the study of multi-particle systems has been a successful area. Many of the underlying structures and phenomena are still at the basis of other, more complex technical systems. What fundamental limitations arise that are to be taken into account when designing cooperative systems?

These four aspects can be 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.