Paradigmenübergreifende Netzwerkalgorithmen: zwei Fliegen mit einer Klappe schlagen

Netzwerke unterschiedlicher Art lassen sich anhand Punkten und Linien abbilden, wobei letztere Punktepaare miteinander verbinden. In sozialen Netzwerken etwa stehen Punkte für Personen, befreundete Personen sind durch Linien miteinander verbunden. In Straßennetzen stehen Punkte für Städte, die Linien für Straßen zwischen den Städten.

Wir wollen auf viele Fragestellungen zu Netzwerken Antworten finden. Welche Route ist zum Beispiel die beste, um von Punkt A nach Punkt B zu gelangen? Oder wer sollte als erstes geimpft werden, um die Ausbreitung einer Infektionskrankheit zu stoppen? Computer können uns bei der Beantwortung dieser Fragen helfen, wenn sie über einen entsprechenden Algorithmus verfügen, einer präzisen Schritt-für-Schritt-Anleitung dazu, wie die Antwort zu finden ist. Doch es gibt unzählige mögliche Algorithmen – so können zehn verschiedene Anwendungen zehn verschiedene Routen ausgeben.

Welche sind die besten Netzwerkalgorithmen?

Diese wissenschaftliche Frage wurde schon vor der Erfindung des Computers untersucht. Die Antworten darauf sind sehr wichtig damit Computernetzwerke funktionieren.

Aber was heißt „die besten“?

Eine klassische Methode zur Bewertung von Algorithmen, die Generationen von Informatikern jahrzehntelang eingesetzt haben, basiert auf dem Begriff der Zeitkomplexität. Sie prognostiziert, wie lange ein Algorithmus gemessen an der Größe einer Eingabe benötigt, um seine Aufgabe zu erledigen. Beispielsweise reicht nach dem Dijkstra-Algorithmus die Zeit zum Lesen der Eingabe auch zur Ermittlung der kürzesten Fahrstrecke von einer Stadt zu einer anderen. Diese Komplexität gilt als bestmöglich, da Computer ohnehin die Eingaben lesen müssen, um die Aufgabe zu erfüllen. Dagegen ist die Ermittlung der Entfernungen zwischen allen Städtepaaren viel schwieriger, und der bisher bekannte beste Algorithmus dafür ist bis zu einer Million Mal langsamer als das Lesen der Eingabe.

Aber Zeitkomplexität ist nicht unbedingt das beste Maß für moderne vernetzte Computer und ihre Eingaben. Man hat viele neue Paradigmen eingeführt, um die Leistung von Algorithmen auf vernetzten Computern besser vorhersagen zu können. So sind beispielsweise in Rechenzentren die Daten auf zahlreichen Computern verteilt. Bei der Ermittlung der optimalen Route oder anderer Informationen kann die Kommunikation zwischen den Computern sehr viel Zeit beanspruchen. Daher ist die Kommunikationskomplexität mitunter ein besseres Maß. Außerdem sind moderne Daten dynamisch, wie etwa die Fahrzeit, die durch Staus beeinflusst werden kann. Dabei ist die Zeit von Bedeutung, die für die Aktualisierung der Information, wie die neue optimale Route, erforderlich ist, also der Begriff der Aktualisierungszeitkomplexität.

Die Herausforderungen

Die Zunahme vernetzter Computer führt zu einer wachsenden Zahl neuer Berechnungsparadigmen mit unterschiedlichen Verfahren zur Vorhersage der Leistung von Algorithmen. Viele Lösungen, die Wissenschaftler für das alte Paradigma entwickelt haben, sind für die neuen Paradigmen (also insbesondere für vernetzte Computer) nicht mehr brauchbar. Der Dijkstra-Algorithmus galt beispielsweise als der bestmögliche Algorithmus für die Berechnung von Entfernungen, wird aber in verteilten Netzwerken und bei der Verarbeitung dynamischer Daten unannehmbar ineffizient. Mit den neuen Paradigmen sind auch zahlreiche neue Herausforderungen entstanden!

Und die Herausforderung ist sogar noch größer, weil wir bei vielen Fragen nicht einmal gute Lösungen für das alte Paradigma haben!

Wie sieht es z.B. aus, wenn wir nicht nach der Route mit der kürzesten Entfernung fragen, sondern nach einer, bei der ein Elektroauto, das beim Bergabfahren Energie zurückgewinnen kann, den wenigsten Strom benötigt? Diese Anwendungen betreffen Probleme, die seit den Anfängen der Informatik aktiv untersucht, aber nicht vollständig gelöst wurden.

Paradigmenübergreifender Ansatz

Am MPI-INF versuchen wir, die bekannten und die neuen Herausforderungen gleichzeitig zu bewältigen. Unsere langfristige Vision ist es, „paradigmenübergreifende Verfahren“ zu entwickeln, das heißt Algorithmen zu konzipieren, die sich auf viele, unterschiedliche Paradigmen - aber denoch effizient - anwenden lassen, und mit diesen Verfahren zwei Ziele gleichzeitig zu erreichen: (1) Lösungen für seit langem bekannte offene Probleme finden und (2) eine neue Generation von Algorithmen für die neuen Berechnungsparadigmen entwickeln. Unsere Philosophie lautet:

Die Untersuchung ein und derselben Fragestellung aus den Perspektiven mehrerer Berechnungsparadigmen gleichzeitig kann zu neuen Erkenntnissen führen, die sich aus der isolierten Sicht eines einzelnen Paradigmas nicht ergeben.

Dank dieses Ansatzes konnten wir jüngst Lösungen für Probleme finden, bei denen zuvor jahrzehntelang keine Fortschritte erzielt wurden. Darunter ist etwa ein neuer Algorithmus für ein Problem im Zusammenhang mit der Ermittlung von Fahrtrouten, der als beste Veröffentlichung in unserem Fachgebiet ausgezeichnet wurde [2]. Ein anderes Beispiel ist die Analyse der Netzwerkkonnektivität, das heißt der Anzahl der Linien, bei deren Entfernung das Netzwerk getrennt wird. Unsere Forschung brachte die ersten Fortschritte seit zwei Jahrzehnten für dieses Problem im alten Paradigma [5] und effiziente Algorithmen für einige neue Paradigmen wie dem verteilten- [3], dem Streaming- [5], dem parallelen- [4] und dem Quanten-Computing [1] hervor.

Was noch vor uns liegt

Unsere Entdeckungen sind nur die Spitze des Eisbergs. Es gibt viele seit Langem offene Probleme, die wir erst durch die erweiterten Perspektiven der neuen Paradigmen besser zu verstehen beginnen. Neuartige Technologien wie maschinelles Lernen und Quantencomputer werden zur Entstehung noch weiterer Paradigmen führen. Mit diesen gehen dann neue Herausforderungen einher, aber auch Chancen, die alten Probleme durch neue Perspektiven zu verstehen. Mit unserer Forschung wollen wir diese Chancen nutzen, um Antworten auf Fragen zu finden, die sich in der Vergangenheit nicht beantworten ließen.

bibliography