Mathematische Methoden im Verteilten Rechnen

• Antragsteller: Professor Dr. Dmitry Feichtner-Kozlov
• Fachliche Zuordnung: Theoretische Informatik ; Mathematik
• Förderung: Förderung von 2014 bis 2019
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 258519225

Ziel dieses interdisziplinären Projekts ist die Entwicklung neuer mathematischer Werkzeuge zur Analyse verteilter Systeme und die Verbesserung unseres Verständnisses von Komplexität und Berechenbarkeitsschranken im verteilten Rechnen. Nahezu alle Rechnersysteme vom Feueralarm bis hin zu internetweiten Dienstleistungen sind heute verteilte Systeme: sie bestehen aus einer Anzahl von Rechnern, die Berechnungen unabhängig voneinander ausführen und miteinander kommunizieren, um ihre Aktivität zu synchronisieren. Unsere Abhängigkeit von Performance und Verlässlichkeit verteilter Systeme ist imminent.Die Hauptschwierigkeit ist dabei die immense Diversität von verteilten Anwendungen, von Modellen verteilten Rechnens und von performance Metriken bei gleichzeitigem Fehlen mathematischer Werkzeuge zur Behandlung dieser Komplexität. Kürzlich wurde der beeindruckende Versuch gemacht, diesen Herausforderungen zu begegnen: eine Anzahl über lange Zeit offener Fragen in verteilter Berechenbarkeit wurde durch die Anwendung hochmoderner Mathematik, insbesondere Elementen der kombinatorischen und algebraischen Topologie, gelöst. Dies schließt Beweise für die Nichtlösbarkeit so fundamentaler Probleme wie Set Agreement und Renaming in Systemen ohne Wartezeit mit ein. Dennoch betreffen die meisten dieser herausragenden Resultate im verteilten Rechnen Existenzaussagen positiver wie negativer Art, d.h. man zeigt, dass für ein gegebenes Problem in gegebenem Modell keine Lösung existiert, oder man zeigt Existenzaussagen in nicht-konstruktiver Art. Von wenigen Ausnahmen abgesehen gibt es keine überzeugenden Beispiele für die Anwendung spezifizierter mathematischer Werkzeuge zum Design effizienter Algorithmen.Dieser Antrag zielt auf ein besseres Verständnis dafür, was in verteilten Systemen implementiert werden kann und was nicht. Insbesondere wollen wir die Stärken moderner Mathematik für die Konstruktion neuer Algorithmen und scharfer unterer Schranken für verteilte Berechnungsprobleme nutzen.

• DFG-Verfahren: Sachbeihilfen
• Internationaler Bezug: Frankreich
• Beteiligte Personen: Professor Petr Kuznetsov; Professor Michel Raynal