Analyse von verteilten Algorithmen und Prozessen in Populati

Dieses Projekt untersucht effiziente Populationsprotokolle für grundlegende Probleme des verteilten Rechnens. Populationsprotokolle wurden von Angluin et al. definiert. Ein solches System besteht aus n anonymen Agenten. Ein Scheduler wählt (in diskreten Zeitschritten) zufällig ein Agentenpaar aus, und diese Agenten dürfen dann interagieren. Sie können einen Zustandsübergang ausführen, der durch einen Algorithmus spezifiziert wird. In diesem Projekt interessieren wir uns für Populationsprotokolle welche grundlegenden Probleme des verteilten Rechnens lösen. Betrachte man als Beispiel den Konsens. Zu Beginn besitzt jeder Agent eine aus k vielen Meinungen. Ziel ist es, einen Zustand zu erreichen, in dem sich alle Agenten auf eine dieser Meinungen einigen. Ein weiteres Beispiel ist die Wahl eines Leaders. Populationsprotokolle werden auch als Modell für chemische Reaktionsnetzwerkeverwendet. Zudemgibt es interessante Beziehungen zwischen Populationsprotokollen, Petri-Netzen und Vektoradditionssystemen. Es gibtauch starke Ähnlichkeiten zwischen einigen biochemischen Regulationsprozessen in lebenden Zellen und Populationsprotokollen. Last but not least können die bekannten SIR- und SIS-Modelle auch als Populationsprotokolle ausgedrückt werden.