Methods for analyzing task solvability in distributed computing

Abstract

Verteiltes Rechnen ist ein Bereich der Informatik, der sich mit Algorithmen und Problemen in Multiagenten-Systemen, beschäftigt. Verteilte Systeme werden mithilfe von Rechenmodellen abstrahiert, bei denen mehrere Prozessoren, die miteinander kommunizieren können, einen Algorithmus (auch Protokoll genannt) ausführen, um eine in der Problemspezifikation festgelegte globale Konfiguration zu erreichen. Im Gegensatz zur traditionellen theoretischen Informatik konzentriert sich das verteilte Rechnen auf jene, durch die Systemeigenschaften bedingten Einschränkungen, die über die individuelle Rechenleistung hinaus gehen. Daher ist die Analyse der Probleme Lösbarkeit eine zentrales Forschungsfrage innerhalb des verteilten Rechnens, da sie eine Klassifizierung von Rechenmodellen erlaubt. In dieser Arbeit stellen wir mehrere Methoden, nämlich kombinatorische, topologische und epistemische Logik, zur Analyse der Lösbarkeit verteilter Probleme vor. Für jedes Framework präsentieren wir Originalergebnisse, die die Fruchtbarkeit des jeweiligen Ansatzes demonstrieren: Wir verwenden das kombinatorische Framework, um die Lösbarkeit von Konsensus in gewissen synchronen, dynamische Netzwerken zu charakterisieren. Das topologische Framework erweist sich als hervorragend geeignet, um eine große Klasseallgemeiner Probleme (“chromatic tasks”) im Iterated Immediate Snapshot-Modell zu charakterisieren. Schlußendlich charakterisieren wir die Lösbarkeit des Firing Rebels (with Relay) Problems in asynchronen verteilten Systemen mithilfe einer Kombination aus epistemischer Logik und graphentheoretischen Werkzeugen. Insgesamt zeigen unsere Ergebnisse, daß es keine “ideale” Analysemethode für den Studium der Problemlösbarkeit in verteilten Systemen gibt.

Distributed computing is a field in computer science dedicated to algorithms and problems (tasks) in multi-agent systems called distributed systems. They are abstracted by means of computational models, where multiple processors must communicate and individually execute an algorithm (also called protocol) to reach a desired global configuration specified as a task. In contrast to more traditional theoretical computer science, distributed computing focuses on the limitations imposed by the system properties beyond computational power. Thus, analyzing task solvability is a core research goal within distributed computing, as it allows to classify the power of computational models.In this thesis, we present several different frameworks, namely, combinatorial, topological, and epistemic logic, for analyzing distributed task solvability. For each framework, we present original results that demonstrate the suitability of the respective approach: We use the combinatorial framework to characterize consensus solvability in synchronous oblivious message adversaries. The topological framework is used to characterize chromatic tasks in the Iterated Immediate Snapshot model. Finally, we characterize the solvability of the Firing Rebels (with Relay) problem in asynchronous message passing via a combination of epistemic logic and graph theoretical tools. Together, our findings reveal that there is no “silver bullet”, i.e., an universally applicable analysis technique, for studying distributed task solvability.