Gracefullly Degrading Agreement in Directed Dynamic Networks

Dieses Projekt ist der Entwicklung von theoretischen Grundlagen, Modellen, Algorithmen und Analysetechniken für verteiltes Agreement in gerichteten dynamischen Netzwerken gewidmet. Solche Netzwerke werden charakterisiert durch (i) eine a priori unbekannte und potentiell zeitvariante Anzahl von Teilnehmern (Prozessen), (ii) eine stark schwankende, richtungsabhängige Konnektivität zwischen Nachbarprozessen, und (iii) das Fehlen einer zentralen Kontrollinstanz. Instantiiert z.B. durch (drahtlose) Sensornetzwerke und ad-hoc Netzwerke sind derartige dynamische Netzwerke immer häufiger in praktischen Anwendungen anzutreffen. Ein natürlicher Ansatz zur Realisierung robuster Services in solchen Anwendungen wäre die Verwendung von Consensus-Algorithmen zwecks Festlegung kritischer Systemparameter wie Zeitplänen, Ausführungsfrequenzen, Ausführungsmoden usw. In größeren dynamischen Netzwerken ist dies jedoch in der Regel unmöglich, da die Lösung von verteiltem Consensus eine gut verbundene und zeitlich ausreichend stabile Netzwerktopologie erfordert. Um diese fundamentale Einschränkung zu überwinden, bietet es sich an, gracefully degrading Varianten von Consensus einzusetzen. Repräsentative Instanzen sind einerseits approximate agreement, wo Entscheidungswerte geringe Abweichungen haben dürfen, und andererseits k-set agreement, wo bis zu k verschiedene Entscheidungswerte erlaubt sind, wenn eine ungünstige Netzwerktopologie z.B. k isolierte Netzwerk-Partitionen erzeugt. Das gegenständliche Projekt ist primär der Suche nach Bedingungen für die Netzwerktopologie gewidmet, die sowohl eine Lösung etwa von k-set agreement erlauben als auch eine ausreichend große Realitätsnähe (Assumption-Coverage) in realen Systemen haben. Daher stehen die Ermittlung schwächster (notwendiger und hinreichender) Bedingungen und die Analyse der resultierenden Assumption Coverage im Vordergrund. Zentrale Bedeutung haben aber natürlich auch entsprechende Lösungsalgorithmen und deren Korrektheitsbeweise. Besonderes Augenmerk wird hier auf die Analyse der Performance gelegt, da es einen Zusammenhang zwischen der Stärke von Lösbarkeitsbedingungen und der Kommunikations- und Speicherkomplexität von Lösungsalgorithmen gibt. Insgesamt soll das Projekt neue Einsichten in die fundamentalen Beschränkungen in dynamischen Netzwerken und neue Algorithmen für die zuverlässige Lösung von verteiltem Agreement unter sehr schwachen Kommunikationsgarantien liefern.

Das Projekt ADynNet (Gracefully Degrading Agreement in Directed Dynamic Networks) war der Entwicklung von theoretischen Grundlagen, Modellen, Algorithmen und Analysetechniken für verteiltes Agreement in gerichteten dynamischen Netzwerken gewidmet. Derartige Netzwerke zeichnen sich durch eine a priori unbekannte und potentiell zeitvariante Anzahl von Teilnehmern, eine stark schwankende, richtungsabhängige Konnektivität zwischen den Teilnehmern, und das Fehlen einer zentralen Kontrollinstanz aus. In Form von drahtlosen Sensornetzwerken und ad-hoc Netzwerken sind derartige dynamische Netzwerke immer häufiger in praktischen Anwendungen anzutreffen. Ein natürlicher Ansatz zur Realisierung robuster Services in solchen Systemen ist die Verwendung von Consensus-Algorithmen für die Festlegung kritischer Systemparameter wie Zeitplänen, Ausführungsfrequenzen und Betriebsarten. In größeren dynamischen Netzwerken wurde dies jedoch als praktisch unmöglich angesehen, da man davon ausging, daß Consensus eine gut verbundene und zeitlich stabile Netzwerktopologie erfordert. Das Projekt ADynNet hat gezeigt, daß dies nicht notwendigerweise der Fall ist: Unsere Untersuchungen haben neue Einsichten in die fundamentalen Beschränkungen sowie neue Algorithmen für verteiltes Agreement in unidirektionalen dynamischen Netzwerken geliefert, die von starken Message Adversaries kontrolliert werden. Einige zentrale Ergebnisse sind: (i) Eine präzise Charakterisierung der Grenze zwischen Unmöglichkeit und Lösbarkeit für Consensus in solchen dynamischen Netzwerken. Überraschenderweise hat sich Punktmengentopologie als die hierfür geeignete mathematische Disziplin erwiesen. (ii) Mehrere neue Consensus-Algorithmen für stabilisierende Message Adversaries, inklusive optimaler Lösungen für sehr kurze Phasen der Stabilität, sowie schwächere Agreement-Algorithmen wie etwa degradierendes k-Set Agreement und Approximate Agreement für Message Adversaries, die keine Lösung von Consensus erlauben. Zusätzlich zu diesen primären Forschungsergebnissen hat die Projektarbeit in ADynNet auch die Nützlichkeit einer wissensbasierten Analyse und epistemischer Logik für die relevanten Probleme zutage gefördert, die schlußendlich ein transdisziplinäres FWF-Folgeprojekt ByzDEL (Reasoning about Knowledge in Byzantine Distributed Systems, P33600) stimuliert haben.