On the strongest message adversary for directed dynamic networks

Abstract

Inspiriert durch die Definition des Weakest Failure Detectors in Asynchronous Message Passing Systems begeben wir uns auf die Suche nach dem Strongest Message Adversary in Synchronous Message Passing Systems. Dafür müssen wir natürlich zuerst festlegen, was ’stronger’ im Kontext von Message Adversaries überhaupt bedeutet. Ähnlich wie im Asynchrous Message Passing Model vergleichen wir Message Adversaries, indem wir einen Message Adversary auf einem anderen Message Adversary simulieren. Die formale Basis für diese Arbeit ist eine Erweiterung des HO-Models, das von Charron-Bost und Schiper eingeführt wurde. Nach der formalen Definition einer Simulation eines Message Adversaries präsentieren wir einen Algorithmus der den Message Adversary STAR auf jedem Message Adversary, der eine Lösung für Consensus erlaubt, simulieren kann. Das impliziert, nach unserer Definition, dass der Message Adversary STAR ein Top Element in der induzierten Quasi-Ordnung ist. Wir führen weiter aus, dass es nicht nur einen ’strongest’ Message Adversary gibt, sondern eine Menge an ’strongest’ Message Adversaries, und charakterisieren diese. Danach besprechen wir die Beziehung der ’strongest’ Message Adversaries zu dem Weakest Failure Detector und die Relation zu den paradoxen Resultaten aus (Biely et.al, Theoretical Computer Science, 2018), die durch unsere verfeinerte theoretische Basis aufgelöst werden können. Schlussendlich definieren und beweisen wir eine speichereffizientere Reduktion von Multi-Valued Consensus auf Binary Consensus, die einen zentralen Baustein in unserer Message Adversary Simulation darstellt.

Inspired by the chase for the weakest failure detector in asynchronous message passing systems, we look for the strongest message adversary in the synchronous setting. This first requires defining the notion of a ’stronger’ message adversary and, similar to the asynchronous model, building a pre-order by simulating a message adversary on top of another message adversary. The formal basis for this thesis is an extended version of the HO-model introduced by Charron-Bost and Schiper. After stating a validity criterion for simulated runs, i.e., a correct message adversary simulation, we present an algorithm that can simulate the message adversary STAR atop of any message adversary that allows to solve consensus. This implies that STAR is a top element in our relation and thus named a ’strongest’ message adversary. However, rather than a single strongest message adversary, it turns out that there is a set of strongest message adversaries, which we characterize fully. After discussing the relation of a strongest message adversary to the weakest failure detector, we elaborate on a seemingly paradoxical result presented in (Biely et.al., Theoretical Computer Science, 2018) and resolve it by means of our refined theoretical basis. Finally we provide and prove correct a more memory efficient reduction of multi-valued consensus to binary consensus, which forms a crucial building block in our message adversary simulation and also provides a practical example for the utility of message adversary simulations that might be of independent interest.