Title: Failure detection in sparse networks
Language: English
Authors: Hutle, Martin 
Qualification level: Doctoral
Advisor: Freiling, Felix 
Assisting Advisor: Schmid, Ulrich
Issue Date: 2005
Number of Pages: 111
Qualification level: Doctoral
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.
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.
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.
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.
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.

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.
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.
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.
Gerade letzteres scheint eine sehr interessante Zusammenführung zweier verschiedener Ansätze der Fehlertoleranz zu sein, die bisher noch nicht ausreichend betrachtet wurde.
URI: https://resolver.obvsg.at/urn:nbn:at:at-ubtuw:1-21522
http://hdl.handle.net/20.500.12708/12762
Library ID: AC04801388
Organisation: E182 - Institut für Technische Informatik (Embedded Computing Systems Group) 
Publication Type: Thesis
Hochschulschrift
Appears in Collections:Thesis

Files in this item:

File Description SizeFormat
Failure detection in sparse networks.pdf580.49 kBAdobe PDFThumbnail
 View/Open
Show full item record

Page view(s)

15
checked on Feb 18, 2021

Download(s)

42
checked on Feb 18, 2021

Google ScholarTM

Check


Items in reposiTUm are protected by copyright, with all rights reserved, unless otherwise indicated.