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

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