Topological characterization of simplex agreement

Mit dem Asynchronous Computability Theorem von Herlihy und Shavit wurden topologische Werkzeuge systematisch in der Theorie des verteilten Rechnens etabliert. Besonders häufig wurden sie zur Untersuchung von verteilten Aufgaben wie dem Approximate Agreement in asynchronen Systemen, die auf einem gemeinsamen Speicher basieren, eingesetzt. In dieser Arbeit untersuchen wir mithilfe des Asynchronous Computability Theorem die Aufgaben Simplex-Agreement auf simplizialen Komplexen sowie Clique-Agreement auf Graphen. Unser Hauptergebnis besagt, dass Simplex Agreement auf einem simplizialen Komplex A für beliebig viele Prozesse genau dann lösbar ist, wenn A kontrahierbar ist. Damit beweisen wir eine Vermutung von Ledent. Allgemeiner charakterisieren wir die Lösbarkeit im wait-free und im t-resilient Modell anhand topologischer Zusammenhangseigenschaften von A. Da Clique Agreement auf einem Graphen G äquivalent zu Simplex Agreement auf dem zugehörigen Kliquenkomplex K(G) ist, ergeben sich daraus unmittelbar entsprechende Lösbarkeitskriterien für Clique Agreement. Darüber hinaus untersuchen wir stärkere graphbasierte Varianten, darunter Shortest-Path Agreement und Minimal-Path Agreement, und zeigen, dass eine Verschärfung der Validitätsbedingung die Aufgabe strikt schwieriger lösbar machen kann. Insbesondere zeigen wir anhand eines geeigneten Graphen, dass sich die Aufgaben des Shortest-Path-Agreement und des Clique-Agreement in ihrer Lösbarkeit unterscheiden.