Verteilte Algorithmen für fundamentale Probleme auf Graphen

Dieses Projekt zu verteilten Netzwerkalgorithmen ist in der Algorithmentheorie angesiedelt. Es handelt sich dabei um einen Bereich der Grundlagenforschung, der sich mit effizienten Berechnungsmethoden beschäftigt. Effizient bedeutet hier, dass möglichst wenig Ressourcen wie Zeit, Speicherplatz oder Energie verbraucht werden sollen. Die theoretischen Untersuchungen in der Algorithmik setzen dort an, wo mit reiner Programmierfertigkeit keine wesentlichen Fortschritte mehr erzielt werden können und stattdessen mathematisches Know-how benötigt wird, um weitere Verbesserungen zu erzielen. Motiviert durch große dezentrale Rechnernetze, wie das Internet of Things, ist das Ziel dieses Projekts die Entwicklung von Algorithmen für Netzwerke, die so groß sind, dass die einzelnen Komponenten nur ihre lokale Umgebung kennen. Man spricht dabei von verteilten Netzwerken, in denen jede Berechnung so durchgeführt werden muss, dass individuelle Komponenten nur mit ihren direkten Nachbarn kommunizieren können. Diese Anforderungen können auch mathematisch präzise modelliert werden. Trotz dieser beschränkten Möglichkeit der lokalen Interaktion sollen in diesem Projekt Algorithmen für globale Fragestellungen entwickelt werden. Überspitzt formuliert also: Think global, act local! Insbesondere wird an Algorithmen zum Finden der schnellsten Verbindungen im Netzwerk und zum optimalen Transport von Gütern geforscht werden. Bildlich gesprochen sollen also für große, komplexe Netzwerke Systeme zur Navigation und zur Durchführung von Logistik aufgebaut werden. Methodisch zeichnet sich dieses Projekt dadurch aus, dass für die neu zu entwickelnden Algorithmen Verfahren aus der numerischen Optimierung angewendet werden sollen. Ausgehend von einer 2015 mit dem Gödel-Preis ausgezeichneten Arbeit von Spielman und Teng wurden insbesondere in den letzten Jahren Methoden entwickelt, um für bestimmte Klassen von Gleichungssystemen sehr schnell Näherungslösungen zu berechnen. Es wurde außerdem gezeigt, dass diese Klassen von Gleichungssystemen hilfreich für die Lösung von Netzwerkproblemen sein können. Dies mag auf den ersten Blick überraschend erscheinen, da es sich bei Gleichungssystemen und abstrakten Netzwerken um zwei grundlegend verschiedene mathematische Objekte handelt. Jedoch beziehen sich die bestehenden Vorarbeiten zum größten Teil nur auf nicht-lokale Berechnungen und sind daher für verteilte Netzwerke nicht geeignet. In diesem Projekt sollen die bestehenden Ideen nun so erweitert werden, dass damit auch verteilte Algorithmen entwickelt werden können.

Dieses Projekt zu verteilten Netzwerkalgorithmen ist in der Algorithmentheorie angesiedelt. Es handelt sich dabei um einen Bereich der Grundlagenforschung, der sich mit effizienten Berechnungsmethoden beschäftigt. Effizient bedeutet hier, dass möglichst wenig Ressourcen wie Zeit, Speicherplatz oder Energie verbraucht werden sollen. Die theoretischen Untersuchungen in der Algorithmik setzen dort an, wo mit reiner Programmierfertigkeit keine wesentlichen Fortschritte mehr erzielt werden können und stattdessen mathematisches Know-how benötigt wird, um weitere Verbesserungen zu erzielen. Motiviert durch große dezentrale Rechnernetze, wie das Internet of Things, war das Ziel dieses Projekts die Entwicklung von Algorithmen für Netzwerke, die so groß sind, dass die einzelnen Komponenten nur ihre lokale Umgebung kennen. Man spricht dabei von verteilten Netzwerken, in denen jede Berechnung so durchgeführt werden muss, dass individuelle Komponenten nur mit ihren direkten Nachbarn kommunizieren können. Trotz dieser beschränkten Möglichkeit der lokalen Interaktion wurden in diesem Projekt Algorithmen für globale Fragestellungen entwickelt. Überspitzt formuliert also: "Think global, act local!" Im Hauptstrang dieses Projekts wurden Algorithmen zum optimalen Transport von Gütern entwickelt, die Verfahren aus der numerischen Optimierung anwenden. Ausgehend von einer 2015 mit dem Gödel-Preis ausgezeichneten Arbeit von Spielman und Teng wurden in zahlreichen Vorarbeiten Methoden entwickelt, um für bestimmte Klassen von Gleichungssystemen sehr schnell Näherungslösungen zu berechnen. Es wurde außerdem gezeigt, dass diese Klassen von Gleichungssystemen hilfreich für die Lösung von Netzwerkproblemen sein können. Jedoch beziehen sich die bestehenden Vorarbeiten zum größten Teil nur auf nicht-lokale Berechnungen und waren daher für verteilte Netzwerke nicht geeignet. In diesem Projekt wurden die bestehenden Ideen nun so erweitert werden, dass damit auch verteilte Algorithmen entwickelt werden konnten. Weitere zentrale Ergebnisse wurden in der Entwicklung einfacher Protokolle zur Ausbreitung von Information oder dem Treffen von Entscheidungen erzielt, die teilweise Anknüpfungspunkte zu Graph Neural Networks haben. Desweiteren wurde eine allgemeine Methode entwickelt um "zentralisierte" Quantenalgorithmen auf ganze Quantennetzwerke zu übertragen, in denen die zwischen Nachbarn ausgetauschten Nachrichten aus Qubits statt klassischer Bits bestehen. Wie in dieser Art von Forschung üblich wurden "auf dem Weg" außerdem zahlreiche mathematische Strukturen auf Netzwerken untersucht und verbessert, die auch zu Verbesserungen für Algorithmen außerhalb des Szenarios verteilter Netzwerke geführt haben. Dies betrifft insbesondere Strukturen, die mit kleinen Teilnetzwerken zentrale Eigenschaften eines Netzwerks approximieren.