Topology in Distributed Computing

Abstract

Topologie ist die mathematisch adäquate Art, um über Konvergenz zu sprechen.<br />Distributed Computing ist das formale Studium von verteilten Systemen.<br /> Die Arbeit beschäftigt sich mit zwei Anwendungen der Topologie im Bereich des Distributed Computing: (1) Mengentheoretische Topologie und (2) algebraische Topologie.<br />Erstere wird verwendet, um die topologische Struktur von unendlichen Bäumen, die die Information über mögliche Ausführungen der Algorithmen subsumieren, zu untersuchen.<br /> Dieses Wissen wird verwendet, um einen einheitlichen Beweis der Unmöglichkeit von Distributed Consensus in mehreren Systemmodellen zu geben.<br />Consensus ist das Einigen aller Prozesse des Systems auf einen einzigen Wert. Zweitere wird verwendet, um die kombinatorische Struktur von Konfigurationen, also der Zusammenfassung aller lokaler Zustände der Prozesse, zu untersuchen.<br />Hierbei wird eine Konfiguration als Simplex in einem Simplizialkomplex aufgefasst.<br /> Die topologische Unvereinbarkeit solcher Komplexe ermöglicht einen Beweis der Unmöglichkeit von k-Set Agreement in gewissen Systemen.<br /> Das ist eine Verallgemeinerung des Consensus-Problems:<br /> Es wird nicht mehr verlangt, dass sich die Prozesse auf nur einen Wert einigen, sondern es wird erlaubt, dass bis zu k unterschiedliche Werte auftreten.<br />

Topology is the general mathematical theory of convergence.<br /> Distributed computing is the formal investigation of communicating concurrent processes.<br /> We explore applications of topology to distributed computing in two directions: (1) Point-set topology and (2) algebraic topology.<br />We use the former to study the topological structure of infinite execution trees.<br /> This enables us to unify a number of impossibility proofs, in particular, the impossibility of distributed consensus-the task of all processes in a system agreeing on a single value-in various (close to) asynchronous systems with crash failures.<br />The latter is used to look into the combinatorial structure of configurations, i.e., the collection of current process states in the system.<br /> Configurations are regarded as simplices in a simplicial complex, and topological incompatibility of such complexes is utilized to prove the impossibility of a generalization of distributed consensus in certain systems.<br /> The particular problem considered is k$set agreement, which is the task of letting all processes agree to values within a set of at most k elements.