Pavlovic, M. (2012). Implementation of a distributed computation framework [Diploma Thesis, Technische Universität Wien]. reposiTUm. http://hdl.handle.net/20.500.12708/159720
Im Paper ``On Dynamic Distributed Computing'' von Sébastien Gambs, Rachid Guerraoui, Florian Huc and Anne-Marie Kermarrec werden neue Algorithmen präsentiert, die es möglich machen, zuverlässige verteilte Berechnungen in einem Computernetzwerk durchzuführen, das seine Zusammensetzung dynamisch ändert. Dabei wird eine unvernachlässigbar große Anzahl an byzantinischen Fehlern toleriert. Die Menge der Knoten des Netzwerks wird partitioniert, wobei ein Element dieser Partition ein Cluster genannt wird und die Größe eines Clusters polylogarithmisch in der Gesamtanzahl der Knoten des Netzwerks ist. Mit großer Wahrscheinlichkeit ist dabei die Mehrheit der Knoten eines Clusters korrekt. Mit Hilfe dieser Cluster, die durch ein randomisiertes logisches Netzwerk verbunden werden, kann man über das zugrundeliegende Netzwerk abstrahieren und in dem Abstrakten Netzwerk zuverlässige Berechnungen durchführen, wobei alle Knoten des Abstrakten Netzwerks als korrekt angenommen werden können. Das Hinzufügen und Entfernen von Knoten zur Laufzeit wird unterstützt, wobei ein polynomialer (bezogen auf die Anfangsgröße des Netzwerks) Anstieg der Gesamtanzahl der Knoten möglich ist. Dieses Dokument beschreibt die erste Implementierung der erwähnten Algorithmen. Obwohl die Implementierung nicht vollständig ist, funktioniert sie mit gewissen Einschränkungen und stellt eine Grundlage für zukünftige Erwerterungen dar. Wir beschreiben Herausforderungen, die während der Implementierung aufgetreten sind, zusätzliche Annahmen über die Knoten, das Netzwerk und mögliche Fehler, sowie mögliche Wege, um diese Annahmen durch das Erweitern der Implementierung fallen lassen zu können.
A recent paper ``On Dynamic Distributed Computing'' by Sébastien Gambs, Rachid Guerraoui, Florian Huc and Anne-Marie Kermarrec presents new algorithms that make it possible to perform reliable distributed computation on a dynamic network of nodes, despite a Byzantine adversary controlling an important fraction of the nodes. The network is partitioned into clusters of small size (polylogarithmic in the size of the network) that contain a majority of honest nodes with high probability. The clusters, interconnected by a randomized overlay network, provide an abstraction which makes it possible to perform reliable computation in a network containing unreliable nodes. The algorithms handle dynamic node addition and removal, as long as the size of the network changes polynomially with respect to its initial size. This document describes the first attempt to implement these algorithms. Although the implementation is not complete, it is usable under certain assumptions and provides a solid basis for future improvements. We discuss the challenges encountered during implementation, the assumptions that had to be made on the network and the adversary and possible ways to weaken or drop these assumptions by further improving the implementation.
