Knowledge and communication complexity in distributed systems

Abstract

Diese Arbeit behandelt die Verbindung zwischen Wissen und Kommunikations-Komplexität in verteilten Systemen: Wir möchten eine untere Schranke für die Komplexität der Kommunikation ermitteln, die benötigt wird um ein Problem P zu lösen. Dazu verfolgen wir einen zweistufigen Ansatz: Zuerst ermitteln wir das Wissen, das die Prozesse benötigen, um P zu lösen. Ausgehend von dem a priori Wissen der Prozesse schließen wir darauf, was die Prozesse lernen müssen, um dieses benötigte Wissen zu erlangen. In einem zweiten Schritt wird die Kommunikation-Komplexität ermittelt, die für diesen Lernvorgang mindestens erforderlich ist. Insbesondere untersuchen wir die Lücke zwischen Action Models, die in Dynamic Epistemic Logic verwendet werden, um Änderungen im epistemischen Zustand eines Systems zu formalisieren, und Kommunikations-Komplixität, konkret, wir schlagen eine Methode vor, um eine untere Schranke für die Anzahl der Bits zu finden, die gesendet werden müssen, um ein Action Model in einer allgemeinen Situation anzuwenden. Darüberhinaus soll diese Arbeit die Suche nach einem stärksten Message Adversary für Konsensus in gerichteten dynamischen Netzwerken unterstützen. Wir wenden daher unsere Methode auf ein Zwei-Prozess-System an, um eine untere Schranke für die Kommunikations-Komplexität dieses Problems zu finden. Allerdings stellt sich heraus, dass die Kommunikations-Komplexität für Konsensus in gerichteten dynamischen Netzwerken unbeschränkt ist. Dennoch liefern wir, als Nebenprodukt unserer Analyse, Bedingungen an den Message Adversary, die notwendig und hinreichend dafür sind, dass zwei Prozesse in einem gerichteten dynamischen Netzwerk Konsensus lösen können.

This thesis is concerned with the connection between knowledge and communication complexity in distributed systems. To find a lower bound on communication complexity for a problem P, we pursue a two-step approach: First we determine the necessary knowledge the processes must locally acquire to solve P. From this required knowledge and the processes’ a priori knowledge, we can infer what the processes have to learn throughout the execution. From this learning process, we can determine a lower bound on communication complexity. More specifically, we bridge the gap between Action Models, used in Dynamic Epistemic Logic to update the epistemic state of the system, and communication complexity and propose a way to determine a lower bound on the number of bits that need to be sent applying an action model in the general setting. As this thesis shall also support the chase for a strongest message adversary for the problem of solving consensus in directed dynamic networks, we apply our method in the case of two processes to find a lower bound on the communication complexity for this problem. It turns out, however, that there is no such bound. Nevertheless, as a by-product of our analysis, we provide necessary and sufficient conditions for a message adversary that allows to solve consensus in a directed dynamic network of two processes.