Topologische Charakterisierung des Konsenses in verteilten Systemen

Wir bieten eine vollständige Charakterisierung sowohl der einheitlichen als auch der nicht-einheitlichen deterministischen Konsenslösbarkeit in verteilten Systemen mit benignen Prozess- und Kommunikationsfehlern unter Verwendung der Punktmengen-Topologie. Genauer gesagt erweitern wir nicht-trivial den Ansatz von Alpern und Schneider aus dem Jahr 1985, indem wir neuartige fehlerbewusste Topologien im Raum unendlicher Ausführungen einführen: die Prozessansicht-Topologie, die durch eine Distanzfunktion induziert wird, die sich auf die lokale Ansicht eines bestimmten Prozesses in einer Ausführung stützt, und die Minimale Topologie, die durch eine Distanzfunktion induziert wird, die sich auf die lokale Ansicht des Prozesses konzentriert, der als letzter zwei Ausführungen unterscheidet. Konsens ist in einem bestimmten Modell genau dann lösbar, wenn die Mengen admissibler Ausführungen, die zu verschiedenen Entscheidungswerten führen, in diesen Topologien nicht verbunden sind. Durch die Anwendung unseres Ansatzes auf eine breite Palette verschiedener Anwendungen bieten wir eine topologische Erklärung für eine Reihe bestehender Algorithmen und Unmöglichkeitsergebnisse und entwickeln mehrere neue, einschließlich einer allgemeinen Äquivalenz der starken und schwachen Gültigkeitsbedingungen.