©ERC
WORUM GEHT ES BEI OLA-TOPSENS?
Angesichts des rasanten Wachstums von Datensätzen und Netzgrößen in den letzten zehn Jahren besteht kaum ein Zweifel daran, dass die Zukunft der Berechnung verteilt sein wird. Ein zentraler Aspekt, der im Mittelpunkt verteilter Algorithmen steht, ist die Frage der Lokalität: Was kann unter Verwendung nur lokaler Informationen berechnet werden, und wie viele Informationen sind dafür erforderlich? Die Beantwortung dieser Frage ist nicht nur entscheidend für die Entwicklung hocheffizienter Algorithmen für viele wichtige verteilte Probleme—wie etwa das Lastenausgleich in riesigen Netzwerken—, sondern die Lokalität ist auch ein grundlegend wichtiger Begriff in vielen anderen Bereichen der Algorithmik, wie etwa bei klassischen sequentiellen Algorithmen, massiv parallelen Algorithmen, dynamischen Algorithmen, sublinearen Algorithmen, Streaming-Algorithmen oder Online-Algorithmen.
Im Kontext verteilter Algorithmen zeigt eine sorgfältige Analyse jüngster Forschungsergebnisse zu Unmöglichkeiten die wesentlichen Herausforderungen beim Verständnis der Lokalität auf—und damit auch beim Entwurf optimaler Algorithmen—für viele Graphprobleme: zu verstehen, 1) wie baumartige Strukturen effizient gelöst werden können und 2) wie algorithmisch jede Abweichung von einer baumartigen Topologie explizit ausgenutzt werden kann. Ziel dieses Vorschlags ist es, ein fundamentales Verständnis der Lokalität durch das neuartige Konzept der topologie-sensitiven Algorithmen zu erlangen, das diese zentralen Herausforderungen angeht, indem es lokale topologische Merkmale in der Eingabeinstanz explizit ausnutzt. Ein solches Verständnis wird zu optimalen Algorithmen und engen Komplexitätsgrenzen für viele wichtige verteilte Probleme führen, wodurch zentrale Fragen in verteilten Algorithmen gelöst werden, die seit Jahrzehnten offen sind, die Grundlagen für hocheffiziente und skalierbare Algorithmen in riesigen Netzwerken gelegt werden und signifikante Verbesserungen gegenüber dem aktuellen Stand der Technik in einer Vielzahl anderer algorithmischer Felder impliziert werden. Kurz gesagt, zielt das vorgeschlagene Projekt auf eine Welt ab, in der alles, was lokal erledigt werden kann, auch lokal erledigt wird.
©ERC
WORUM GEHT ES BEI OLA-TOPSENS?
Angesichts des rasanten Wachstums von Datensätzen und Netzgrößen in den letzten zehn Jahren besteht kaum ein Zweifel daran, dass die Zukunft der Berechnung verteilt sein wird. Ein zentraler Aspekt, der im Mittelpunkt verteilter Algorithmen steht, ist die Frage der Lokalität: Was kann unter Verwendung nur lokaler Informationen berechnet werden, und wie viele Informationen sind dafür erforderlich? Die Beantwortung dieser Frage ist nicht nur entscheidend für die Entwicklung hocheffizienter Algorithmen für viele wichtige verteilte Probleme—wie etwa das Lastenausgleich in riesigen Netzwerken—, sondern die Lokalität ist auch ein grundlegend wichtiger Begriff in vielen anderen Bereichen der Algorithmik, wie etwa bei klassischen sequentiellen Algorithmen, massiv parallelen Algorithmen, dynamischen Algorithmen, sublinearen Algorithmen, Streaming-Algorithmen oder Online-Algorithmen.
Im Kontext verteilter Algorithmen zeigt eine sorgfältige Analyse jüngster Forschungsergebnisse zu Unmöglichkeiten die wesentlichen Herausforderungen beim Verständnis der Lokalität auf—und damit auch beim Entwurf optimaler Algorithmen—für viele Graphprobleme: zu verstehen, 1) wie baumartige Strukturen effizient gelöst werden können und 2) wie algorithmisch jede Abweichung von einer baumartigen Topologie explizit ausgenutzt werden kann. Ziel dieses Vorschlags ist es, ein fundamentales Verständnis der Lokalität durch das neuartige Konzept der topologie-sensitiven Algorithmen zu erlangen, das diese zentralen Herausforderungen angeht, indem es lokale topologische Merkmale in der Eingabeinstanz explizit ausnutzt. Ein solches Verständnis wird zu optimalen Algorithmen und engen Komplexitätsgrenzen für viele wichtige verteilte Probleme führen, wodurch zentrale Fragen in verteilten Algorithmen gelöst werden, die seit Jahrzehnten offen sind, die Grundlagen für hocheffiziente und skalierbare Algorithmen in riesigen Netzwerken gelegt werden und signifikante Verbesserungen gegenüber dem aktuellen Stand der Technik in einer Vielzahl anderer algorithmischer Felder impliziert werden. Kurz gesagt, zielt das vorgeschlagene Projekt auf eine Welt ab, in der alles, was lokal erledigt werden kann, auch lokal erledigt wird.
