Real-time performance analysis of synchronous distributed systems

Abstract

Eine der zentralen Fragen der Informatik ist, wie lange ein Algorithmus braucht, um seine Aufgabe zu erfüllen. Während diese Frage in (zentralisierten) sequenziellen Algorithmen bereits ausgiebig untersucht wurde, sind in verteilten Algorithmen noch viele Fragen zur Zeitkomplexität offen. In synchronen rundenbasierenden verteilten Algorithmen stellt die Rundenanzahl bis zur Termination ein zur klassischen Zeitkomplexität analoges Maß dar, jedoch werden dabei viele Feinheiten unter den Teppich gekehrt, die zum Beispiel durch Fehler, das Kommunikationssystem oder Ungewissheiten der zeitlichen Abfolgen durch Asynchronität während einer Runde auftreten. Die vorliegende Arbeit stellt eine neuartige Analyse verteilter Systeme vor, die mehrere unabhängige verteilte Algorithmen nebenläufig auf einer gemeinsamen Kommunikationsinfrastruktur ausführen. Dabei wird besonders auf die bereits angesprochenen Ungewissheiten der zeitlichen Abfolgen eingegangen und die Leistungsfähigkeit der Algorithmen in Bezug auf das Echtzeitverhalten analysiert. Das Hauptaugenmerk liegt dabei auf den Interna einer Runde, konkret dem Senden und Empfangen von Nachrichten, die mit verschiedenen mathematischen Werkzeugen analysiert werden. Um den Zugriff der Algorithmen auf die gemeinsam verwendeten Kommunikationskanäle zu steuern, wird ein Echtzeitscheduler verwendet. Geeignete Fehlertoleranz-Mechanismen erlauben es, verloren gegangene Nachrichten in synchronen verteilten Algorithmen zu tolerieren. Daher können Nachrichten als Arbeitspakete aufgefasst werden, die als Bearbeitungsfrist das Ende der Runde haben. Ein guter Echtzeitscheduler versucht, den kumulativen Ertrag zu maximieren, den er durch die fristgerechte Bearbeitung der Pakete erhält. Seine Konkurrenzfähigkeit wird üblicherweise in Relation zu einem optimalen hellseherischen Scheduler gemessen, der in die Zukunft sehen kann. Diese Arbeit legt den Grundstein für eine neue Methode zur automatischen Analyse der Konkurrenzfähigkeit von Schedulingalgorithmen. Dabei wird das Problem bei vorgegebenen Arbeitspakettypen auf das Finden von Kreisen mit minimalem durchschnittlichen Gewicht in einem Graphen reduziert. Weiters, wenngleich mit sehr großem Rechenaufwand verbunden, kann durch algorithmische Spieltheorie ein optimaler Schedulingalgorithmus synthetisiert werden. Auf der Empfängerseite kommt ein Synchronisationsalgorithmus zum Einsatz, der vom Scheduler verworfene gegangenen Nachrichten implizit kompensiert und wieder eine konsistente Rundenstruktur herstellt. Das Zeitverhalten eines darauf aufbauenden verteilten Algorithmus hängt stark von der Leistungsfähigkeit dieses Synchronisationsalgorithmus ab. Eine Abstraktion der verworfenen (oder sonstwie verlorengegangenen) Nachrichten in einem probabilistischen Kommunikations-Fehlermodell ermöglicht die Anwendung von Markoff-Theorie zur Berechnung der zu erwarteten Rundendauer. Die Analyse der Folge der Startzeiten der von dem Synchronisieralgorithmus generierten Runden durch die Modellierung als Markoff-Kette liefert schlussendlich Erkenntnisse über die zu erwarteten Rundendauern.

The time it takes for an algorithm to perform its task is a central question in computer science. It has been extensively studied for (centralized) sequential algorithms, while a comprehensive treatment of time complexity in the distributed setting is still lacking. In synchronous round-based distributed algorithms, the number of rounds until the problem is solved represents a performance measure analogous to standard time complexity (Newtonian real-time), but puts under the rug the many intricacies that occur in a round due to faults, message passing, timing uncertainties due to asynchrony etc. This thesis provides a novel framework for analyzing distributed systems running multiple independent distributed algorithms simultaneously on a shared message passing communication infrastructure. In particular, the previously mentioned timing uncertainties are addressed, and the performance of the executed algorithms are analyzed with respect to Newtonian real-time. To do so, the internals of a round, that is, transmitting and receiving messages, must be taken into account. We study these mechanisms with different mathematical tools. On the transmitter side, a real-time scheduler responsible for scheduling the messages of multiple algorithms on the shared communication channels. Since suitable fault-tolerance techniques allow to deal with dropped messages in a synchronous distributed algorithm, messages can be modeled as firm deadline jobs with the end of a round as their deadline. Obviously, a good scheduling algorithm maximizes the cumulative utility gained by the successfully scheduled jobs. The quality of a scheduler is usually characterized by its competitive factor, that is, the performance of the scheduler with respect to an optimal clairvoyant scheduler, that knows the future. This thesis lays the foundation for a new approach to automatically perform the competitive analysis of scheduling algorithms with respect to given task sets. This is done by using a reduction to the problem of finding minimum mean-weight-cycles in multi-objective graphs. In addition, albeit being computationally hard, algorithmic game theory also allows to synthesize optimal scheduling algorithms. On the receiver side, a synchronizer algorithm can be used to maintain a consistent round structure by compensating messages dropped by the scheduler. The performance of a distributed algorithm running atop of such a thus synchronizer directly depends on the performance of the synchronizer. Abstracting dropped (and otherwise lost) messages by a probabilistic link failure model allows to calculate the expected round duration using Markov theory. By analyzing the series of the starting times of the rounds generated by the synchronizer, and by modeling its execution as a Markov chain, this thesis finally develops results regarding the expected round duration.