Models and algorithms for hybrid networks and hybrid programmable matter
Creators: name: Hinnenthal, Kristian
Publisher: name: Universität Paderborn
Year: 2021

description: Diese Dissertation behandelt zwei Typen von hybriden verteilten Systemen, hybride Netzwerke und hybride programmierbare Materie. In hybriden Netzwerken besitzen Knoten verschiedene Kommunikationsmodi. Moderne Mobiltelefone können beispielsweise sowohl Bluetooth-Verbindungen aufbauen, als auch über das zelluläre Netzwerk kommunizieren. Im ersten Teil dieser Dissertation stellen wir ein theoretisches Modell für hybride Netzwerke mit zwei verschiedenen Kommunikationsmodi vor, einem lokalen und einem globalen Modus. Während der lokale Modus die Eigenschaften von vorgegebenen Netzwerken begrenzter Reichweite, wie ad hoc Netzwerken, erfasst, beschreibt der globale Modus die Fähigkeit der Knoten über eine geteilte Infrastruktur, wie dem zellulären Netzwerk, zu kommunizieren. Wir untersuchen die Möglichkeiten und Grenzen eines solchen hybriden Netzwerkes für unterschiedliche Kommunikationsbeschränkungen und präsentieren Algorithmen für verschiedene Probleme. Einer der Schwerpunkte liegt im Studium von Graphproblemen wie der Berechnung kürzester Wege im Graphen der lokalen Kanten. Der zweite Teil dieser Dissertation behandelt hybride programmierbare Materie. Hybride programmierbare Materie setzt sich zusammen aus aktiven Elementen, den Robotern, die sich auf passiven Elementen, den Kacheln, bewegen und diese verschieben können. Die Roboter agieren dabei autonom und ohne globale Informationen und bilden gemeinsam mit den Kacheln eine Art programmierbare Substanz. Wir untersuchen das Shape Formation Problem sowie das Shape Recognition Problem in einem einfachen Modell für hybride programmierbare Materie. Der Fokus unserer Arbeit liegt in der Erforschung der Mächtigkeit eines einzelnen Roboters. Darüber hinaus präsentieren wir grundlegende Erkenntnisse für die Forschung in Systemen mit mehreren Robotern.
description: This dissertation is devoted to the study of two different hybrid distributed systems, hybrid networks and hybrid programmable matter. Hybrid networks are communication networks in which the nodes possess different modes of communication. For example, modern mobile phones can typically communicate both via Bluetooth ad hoc connections as well as the cellular network, but applications rarely leverage both. To study hybrid networks, in the first part of this thesis we establish a theoretical model in which nodes have two different communication modes, a local and a global mode. Whereas the local mode captures characteristics of a limited-range fixed network, such as an ad hoc network, the global mode models the nodes' ability to use a shared infrastructure such as the cellular network. We explore the capabilities and limitations of hybrid networks under different communication restrictions and present algorithms for various problems. As a main focus of the first part, we study the computation of graph problems, and shortest paths in particular, where the input graph is given by the local network. The second part of this dissertation revolves around hybrid programmable matter. Hybrid programmable matter refers to a system of minute robots that operate on a set of tiles, and that can lift and place tiles to alter the structure. The robots are envisioned to act autonomously and without any global information, only based on a simple internal program. Therefore, from the outside, the system behaves as a self-transforming substance. We study two different problems in a simple model for hybrid programmable matter, shape formation and shape recognition. The main focus of our work lies in exploring the power of a single robot, and we lay some foundations to leverage multiple robots that act coordinately.