Analyse verteilter Protokolle im Populationsmodel

Antragstellerin Professorin Dr. Petra Berenbrink
Fachliche Zuordnung Theoretische Informatik
Förderung Förderung seit 2022
Projektkennung Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 491453517
 

Projektbeschreibung

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