Lösbarkeit von Consensus unter Nachrichtengegnern

Abstract

Motiviert durch die zunehmende Allgegenwärtigkeit von kleinen, mobilen, drahtlos kommunizierenden Endgeräten und den daraus resultierenden dynamischen Netzen, beschäftigt sich diese Arbeit mit den theoretischen Grundlagen von verteilten Algorithmen in solchen Systemen. Unser Hauptaugenmerk liegt hier auf der Charakterisierung der Lösbarkeit des klassischen Consensus-Problems in dynamischen Netzen, in denen beliebige Nachrichten verloren gehen können. Dafür verwenden wir das Modell der Nachrichtengegner, welches es uns erlaubt, einen beinahe beliebigen dynamischen Verlust von Nachrichten in einem synchronen System darzustellen. Wir betrachten verschiedene Aspekte dieser Fragestellung, beginnend mit dem verhältnismäßig simplen Fall der grenzwertmäßig abgeschlossenen Nachrichtengegner. Wir gehen dann über zu stabilisierenden Nachrichtengegnern, die diese Eigenschaft nicht besitzen, bevor wir schließlich, mit der Hilfe von Punktmengentopologie, eine Charakterisierung von allgemeinen Nachrichtengegnern präsentieren.