Failure detection in sparse networks

Abstract

One of the most explored approaches to overcome the impossibility of distributed consensus in fully asynchronous systems was the introduction of the concept of unreliable failure detectors by Chandra and Toueg in 1996. Failure detectors emerged not only as theoretical encapsulation of the synchrony needed for consensus, but also as useful building blocks for many distributed algorithms.<br />Therefore, in literature a lot of effort has been spent to implement such failure detectors efficiently. However, almost all currently known solutions are based on the assumption of a fully connected network between the processors of the system.<br />This thesis focuses on the implementation of various failure detectors in sparsely connected networks. Sparse networks model the nature of many non-broadcast networks on a low-level basis, namely wireless ad-hoc networks, sensor networks, and even the Internet. From such an approach, an implementation can profit regarding message complexity and accuracy. However, proving the correctness of a failure detector algorithm in sparse networks showed up to be an elaborating task. The introduction of a local failure detector as a new class of failure detectors with appropriate transformation algorithms to global failure detectors simplifies these things.<br />The failure detector implementations in this work cover several system models that head at distinct goals, including constant message size in arbitrary large networks, weak timing, and self-stabilization.<br />Especially the latter seems to be a very interesting combination of two flavors of fault tolerance---robustness and self-stabilization---which has not been addressed sufficiently in literature.<br />

Einer der meist erforschten Ansätze um die Unlösbarkeit des Consensus Problems in vollständig asynchronen Systemen zu umgehen, ist das 1996 von Chandra und Toueg in einem wegweisenden Artikel vorgestellte Konzept der Fehlerdetektoren. Seither haben sich Fehlerdetektoren nicht nur als theoretische Abstraktion der notwendigen Synchronität für Consensus bewährt, sondern sie bilden auch nützliche Bausteine für viele Algorithmen im Bereich der Fehlertoleranten Verteilten Systeme.<br />Daher findet sich auch in der Literatur eine Menge an Ansätzen, Fehlerdetektoren möglichst effizient zu implementieren. Allerdings basieren praktisch alle bisherigen Lösungen auf der Annahme eines vollverbundenen Netzwerks zwischen den einzelnen Prozessoren des Systems.<br />Diese Arbeit beschäftigt sich mit der Implementierung verschiedener Fehlerdetektoren in Sparse Networks. Unvollständige Graphen modellieren die Gegebenheiten von vielen Low-Level Netzwerken, wie etwa von Wireless Ad-Hoc Networks, Sensor Networks und auch des Internets. Dieser Ansatz erweist sich als sehr nützlich, da---wie diese Arbeit zeigt---Algorithmen nicht nur effizienter werden, sondern auch direkt von dieser Netzwerkstruktur profitieren können. Andererseits sind Beweise in solchen Graphen meist aufwändiger und unübersichtlicher als für vollverbundene Netze. Durch die Einführung von lokalen Fehlerdetektoren und entsprechenden Transformationsalgorithmen zu globalen Fehlerdetektoren können die Beweise einfacher und eleganter werden. Diese Arbeit beleuchtet verschiedene Aspekte von Fehlerdetektorimplementierungen in Sparse Networks: Konstante Nachrichtengröße trotz beliebig großer Netze, geringe Synchronitätsannahmen und die Kombination mit Selbststabilisierung.<br />Gerade letzteres scheint eine sehr interessante Zusammenführung zweier verschiedener Ansätze der Fehlertoleranz zu sein, die bisher noch nicht ausreichend betrachtet wurde.