Kommunikationsprotokolle basierend auf Random Walks

• Antragstellerin: Professorin Dr. Petra Berenbrink
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2019 bis 2023
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 427756233

In den letzten Jahren ist das Interesse an verteilten Algorithmen angestiegen, besondersin den sehr grundlegenden CONGEST- und LOCAL-Modellen. Hier wird das System durch einen ungerichteten und verbundenen Graphen modelliert. Die Knoten dieses Graphen repräsentieren Recheneinheiten und die Kanten repräsentieren bidirektionale Kommunikationsverbindungen. Wir gehen davon aus, dass die Knoten eine eindeutige ID haben. Anfangs kennt jeder Knoten nur seine Nachbarn im Netzwerk. Jeder Knoten ist für die Berechnung eines Teils der Ausgabe verantwortlich. Die Kommunikation erfolgt über das Senden von Nachrichten an die Nachbarn im Graphen. In diesem Projekt betrachten wir eine randomisierte Variante des Modells, in derjeder Knoten pro Schritt mit einer (eventuell einelementigen) Teilende seiner Nachbarnkommunizieren kann. Wir interessieren uns hauptsächlich für Prozesse die, auf der einen oder anderen Art, Informationen im Netzwerk verbreiten: Gossiping, Lastbalancierung und COBRA Walks. Cobra Walks werden gerne benutzt um die Ausbreitung von Krankheiten zu modellieren. Lastverteilung und Gossiping sind zwei grundlegende Aufgaben im Bereich des verteilten Rechnens.Auf den ersten Blick scheinen diese drei Probleme nicht viel miteinander zu tun zu haben.Diese Probleme basieren jedoch alle drei auf einer zugrundeliegenden randomisierten Kommunikationsstruktur, bei der Knoten Nachrichten mit zufällig gewählten Nachbarn austauschen. Die Analyse dieser Prozesse basiert somit häufig auf Techniken aus dem Bereich der Analyse von mehreren parallelen Random Walks. Betrachten wir zum Beispiel das sogenannte Push Model welches oft im Bereich Broadcasting und Gossiping angewendet wird. Hier senden alle Knoten eine Nachricht an genau einen zufällig ausgewählten Nachbarn. Aus der Sicht der Nachrichten sieht es so aus als ob sie einfach einen Random Walk in Graphen machen. Random Walks sind ein bekanntes mathematisches Modell welches für die Analyse von vielfältigen randomisierten Prozessen in Graphen benutzt werden kann.

• DFG-Verfahren: Sachbeihilfen