Dezentralisierte Algorithmen für lokale und globale Probleme

Im letzten Jahrzehnt hat die Theorie der verteilten und massiv parallelen Systeme eine unglaubliche Entwicklung vollzogen. Die Fülle an kürzlich erzielten Resultaten für lokale und globale Graphenprobleme und das Erscheinen neuer algorithmischer Techniken, deren Potential bei Weitem nicht ausgeschöpft ist, schaffen eine Vielzahl von Forschungsmöglichkeiten, die wir mit diesem Antrag verfolgen und im Folgenden beschreiben. In diesem Forschungsvorhaben untersuchen wir grundlegende Aspekte von Algorithmen in verteilten und massiv parallelen Systemen. 1) Unser erstes Ziel ist es, die Entwicklung einer Komplexitätstheorie verteilter Algorithmen, die weit über die beachtlichen Beschränkungen der derzeitigen verteilten Komplexitätstheorie für lokale Graphenprobleme hinausgeht, zu initiieren. Eine voll entwickelte verteilte Komplexitätstheorie hätte erhebliche Auswirkungen auf den Stand der Forschung für viele zentrale Probleme aus dem Bereich des verteilten Rechnens. 2) Wir beabsichtigen, Techniken, die in den letzten Jahren für lokale Probleme entwickelt wurden, für globale Probleme, für die der Einfluss dieser Techniken bisher höchst beschränkt war, zu nutzen. Des Weiteren werden wir die Entwicklung einer verteilten Komplexitätstheorie für Optimierungsprobleme initiieren. 3) Wir beabsichtigen eine massiv parallele Komplexitätstheorie für lokale Graphenprobleme und Optimierungsprobleme zu entwickeln. 4) In jeder dieser Forschungsrichtungen beabsichtigen wir, Algorithmen und Unmöglichkeitsresultate für fundamentale Probleme, wie etwa Load-Balancing-Probleme, Graphenfärbungsprobleme, inklusionsmaximale Matchings und Approximationen für kardinalitätsmaximale Matchings oder kardinalitätsminimale Knotenüberdeckungen, signifikant zu verbessern. Eine zentrale Neuheit unseres Ansatzes ist, dass wir verteilte und parallele Algorithmen gleichzeitig aus einer komplexitätstheoretischen, einer problemzentrierten und einer modellzentrierten Perspektive untersuchen. Zum Beispiel werden wir aus dem modellzentrierten Blickwinkel Methoden entwickeln, die den Wissenstransfer zwischen verteilten und massiv parallelen Systemen automatisieren. Dabei zielen wir auf generische Ansätze ab, die---im Gegensatz zu früheren Resultaten---Wissenstransfer für große Problemklassen auf einmal ermöglichen. Insbesondere wurde der Ansatz, Techniken, die für lokale Probleme entwickelt wurden, zu benutzen, um globale Probleme zu lösen, bisher nicht systematisch untersucht. Die Kombination der unterschiedlichen Perspektiven---von deren Zusammenspiel wir uns einen erheblich Nutzen versprechen---ist ebenfalls neu. Das Forschungsteam besteht aus den beiden PIs (Dr. Sebastian Brandt, Univ.-Prof. Dr. Yannic Maus) und drei über das beantragte Projekt finanzierten Doktorierenden. Das Forschungsvorhaben baut auf der besonderen Kombination der Expertise der beiden PIs auf.