Solving k-Set agreement in dynamic networks

Abstract

In dieser Diplomarbeit stelle ich eine Lösung des "k-set agreement" -Problems unter einem schwachen, verteilten, synchronen Berechnungsmodel vor. Das Model basiert auf einer Sequenz von gerichteten Kommunikationsgraphen, die, vom Adversary bestimmt, vorgibt, welcher Prozess von welchem Prozess pro Runde eine Nachricht erhält. "k-set agreement" beschreibt das Problem, in dem Prozesse mit möglicherweise verschiedenen Startwerten sich auf ein kleineres Set von Entscheidungswerten einigen müssen. Um "k-set agreement" lösbar zu machen, müssen die Möglichkeiten des Adversaries zur Unterbindung der Kommunikation zwischen Prozessen eingeschränkt werden. Diese Restriktionen stellen sicher, dass in jeder Ausführung stark verbundene Strukturen (sogenannte "vertex stable root components") sich gegenseitig beeinflussen und irgendwann ausreichend lang stabil sind, um Termination zu garantieren. Wir geben einen Algorithmus an, der unter diesen Einschränkungen "k-set agreement" löst und beweisen seine Korrektheit. Der Algorithmus versucht, lokal "vertex stable root components" zu erkennen und diese zu nutzen, um alle darin enthaltenen Prozesse zu einer gemeinsamen Entscheidung zu bringen. Der Algorithmus ist k-uniform, also unabhängig von k, und passt daher die Anzahl unterschiedlicher Entscheidungswerte automatisch an die aktuellen Bedingungen im Netzwerk an. Die Resultate dieser Arbeit, die Unterstützung durch das Projekt RiSE (S11405) des österrechischen Fonds zur Förderung wissenschaftlicher Forschung (FWF) erhielt, wurden bei der 17. International Conference on the Principles of Distributed Systems (OPODIS 2013) publiziert.

In this Master thesis, we will propose a way to solve k-set agreement in a very relaxed model of a synchronous distributed system. The model is based on a sequence of directed communication graphs determined by the adversary, which specify which process receives a message from which process in a round. k-set agreement describes the problem where distributed process with possible different initial values have to agree on a smaller set of decision values. In order to make k-set agreement solvable, the power of the adversary w.r.t. disrupting communication between processes must be restricted. Essentially, the proposed restrictions ensure that, during every execution, certain strongly connected subgraphs (vertex stable root components) are influencing each other and that, eventually, communication graphs are sufficiently stable for a short time to ensure termination. We will show that an algorithm exists, which can solve k-set agreement under these weak constraints, and prove its correctness. Basically, the algorithm locally estimates whether a vertex stable root component has formed and, if so, tries to use its strong connectivity to force all its members to decide on the same value. The algorithm is k-uniform, i.e., independent of k, hence automatically adapts the number of different decision values according to the actual network conditions. The result of this work, which has been supported by Austrian Science Fund (FWF) project RiSE (S11405), have been published at the 17th International Conference on the Principles of Distributed Systems (OPODIS 2013).