Analyse verteilter Protokolle im Populationsmodel

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 duch einen Algorithmus spezifiziert wird. In diesem Projekt interessieren wir uns für Populationsprotokolle welche grundlegende Probleme des verteilten Rechnens lösen. Betrachten Sie 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 zum Beispiel als Modell für chemische Reaktionsnetzwerke verwendet. Es gibt interessante Beziehungen zwischen Populationsprotokollen, Petri-Netzen und Vektoradditionssystemen. Es gibt 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.

DFG-Verfahren Sachbeihilfen

Internationaler Bezug Österreich

Partnerorganisation Fonds zur Förderung der wissenschaftlichen Forschung (FWF)

Kooperationspartner Professor Dr. Robert Elsässer