FWF - Bandwidth - Kommunikationseffiziente Verteilte Algorithmen

Weiterer Forschungskontext. Mit dem schnellen Wachstum von Netzwerken und der rasanten Zunahme der Datenmenge werden verteilte Algorithmen in Netzen in Zukunft eine entscheidende Rolle spielen und in fast allen Lebensbereichen relevant sein. Dieses Projekt zielt darauf ab, unser Verständnis für die grundlegenden Aspekte dieser Bereiche zu verbessern. Algorithmen, die in solchen Umgebungen arbeiten, müssen sich mit verschiedenen Formen von Kommunikationsbeschränkungen auseinandersetzen, z.B. durch große Entfernungen zwischen Computern in einem Netzwerk oder Bandbreitenbeschränkungen von Kommunikationsverbindungen. Das Hauptziel dieses Projekts besteht darin, eine grundlegende Theorie zu entwickeln und das Verständnis für die Rolle von Kommunikationsbeschränkungen bei verteilten Berechnungen zu erweitern. Ansatz und Grad der Originalität. Unser Ansatz ist zweigeteilt: Einerseits zielen wir auf die Entwicklung neuer kommunikationseffiziente verteilte Algorithmen zu entwickeln, die zentrale offene Fragen in diesem Bereich, wie z.B. die die Rolle des Zufalls zu verstehen. Dazu müssen wir weit über den aktuellen Stand der Technik hinausgehen, was wir zum Beispiel Methoden zur Derandomisierung und neue Graphenzerlegungen, die für bandbreitenbeschränkte Umgebungen optimiert sind. Andererseits wollen wir die Grenzen des verteilten Rechnens bestimmen. Ein Hauptziel ist es, universelle Gründe für die Schwierigkeit der verteilten Optimierung zu identifizieren. Während solche zentralen Punkte der Härte in der zentralisierten Welt bekannt sind, wäre ein solches Ergebnis in der verteilten Welt neu. Außerdem wollen wir eine Reihe kleinerer, einfacher Probleme lösen, die als Sprungbrett zu diesen größeren Zielen dienen. Kommunikationseffiziente Algorithmen sind oft robust in dem Sinne, dass sie Lösungen in verschiedenen Kom- plexitätsmodellen liefern. Langfristig wird sich dieses Projekt daher auch auf andere Bereiche auswirken, z. B. auf massiv parallele Berechnungsalgorithmen, sublineare Algorithmen, Streaming und lokale Berechnungsalgorithmen. Primär beteiligte Forscher. Das Forschungsteam besteht aus dem PI (Ass. Prof. Yannic Maus, TU Graz) und zwei Doktoranden, die von diesem Projekt finanziert werden. Darüber hinaus wollen wir die bestehende Zusammenarbeit mit internationalen Experten fortzusetzen, die für unser Projekt nützlich sind, und unser Kooperationsnetzwerk zu erweitern.