Verteilte Algorithmen: Ein Forschungsfeld mit viel Potenzial
Eine Familie sitzt an einem Tisch und spielt ein Spiel. Jeder hat ein Blatt Papier vor sich, auf dem eine Zahl steht. Es gilt nun, auf die Rückseite eine weitere Zahl zu schreiben – und zwar so, dass alle dieselbe Zahl schreiben und es eine Zahl ist, die eines der Familienmitglieder auf der Vorderseite notiert hat. Wie das geht? Ganz einfach. Man redet miteinander und kommt so schnell zu einer Lösung. Was ist aber nun, wenn ein Familienmitglied nur sehr leise spricht oder nicht alle hören kann? Oder sich mit der Zeit verändert, wer mit wem sprechen oder wer wen hören kann? Dann wird dieses einfache Spiel zunehmend komplexer und möglicherweise sogar unlösbar.
Diese Situation am Familientisch zeigt ein fundamentales Problem in der Computerwelt auf: Ein globales System, in dem einzelne Teilnehmende miteinander kommunizieren müssen, diese Kommunikation jedoch aus verschiedenen Gründen vorübergehend ausfallen kann. Denken wir dabei zum Beispiel an Rechenzentren, die zwecks Ausfallsicherheit über den Globus verteilt stationiert sind. Damit sich diese räumlich verteilten Rechner nun alle gleich verhalten (und der Ausfall eines der Rechner zu keinem Datenverlust führt), müssen diese miteinander kommunizieren und das eingangs beschriebene Problem am Familientisch lösen. Und diese Kommunikation ist nicht immer perfekt. Genau dort, nämlich beim kooperativen Lösen von Problemstellungen trotz fehlerhafter Kommunikation, setzen verteilte Algorithmen an. Kyrill Winkler kennt sich damit aus. Er ist Entwicklungsingenieur im Bereich Real Time Architectures bei ITK Engineering und betreibt seit mehreren Jahren Grundlagenforschung im Bereich verteilte Algorithmen.
"Die Welt wird zunehmend komplexer. Diese Komplexität ergibt sich unter anderem dadurch, dass vieles nebenläufig passiert. Durch die Auseinandersetzung mit verteilten Algorithmen habe ich gelernt, solche parallelen Vorgänge besser einordnen zu können."
Ein spannendes Resultat für die Forschungscommunity
Ein neues Ergebnis zu eingangs erwähnter Problemstellung hat Kyrill im Jänner auf einer wichtigen Konferenz im Bereich der theoretischen Informatik, der ITCS (Innovations in Theoretical Computer Science) am MIT in Cambridge präsentiert und damit aufgezeigt, wie lange es maximal dauern kann, bis sich alle Teilnehmenden am Tisch einig sind. Consensus – sich einig werden – ist eines der bekanntesten Probleme bei verteilten Algorithmen. Er hat gemeinsam mit seinen Co-Autoren damit einen spannenden Beitrag zu der rund 40jährigen Geschichte des Forschungsfeldes geleistet.
Die Welt verstehen wollen
Kyrill Winkler arbeitet seit etwa eineinhalb Jahren bei der ITK Engineering und ist dort im Bereich Real Time Architectures tätig: „Für mich ist dieser Themenbereich und die ITK Engineering im Allgemeinen extrem spannend. Ich kann mich hier in meiner Arbeit entfalten, unabhängig arbeiten und bekomme viel Unterstützung bei meiner Weiterentwicklung.“ Die Beschäftigung mit verteilten Algorithmen ist für ihn nach seiner universitären Forschungszeit ein Hobby.
Auch wenn die Forschungsergebnisse derzeit noch nicht direkt in die Projekte bei ITK Engineering einfließen, so hat der Informatiker durch das Studium der verteilten Algorithmen eine Denkweise gelernt, die ihm nun im Berufsalltag sehr hilft. „Die Welt wird zunehmend komplexer. Diese Komplexität ergibt sich unter anderem dadurch, dass vieles nebenläufig passiert. Durch die Auseinandersetzung mit verteilten Algorithmen habe ich gelernt, solche parallelen Vorgänge besser einordnen zu können.“
Um Laien die Herausforderung von parallelen Abläufen besser verständlich zu machen, zieht er den Vergleich des Kochens heran: „Wenn ich Nudeln koche, ist das relativ einfach. Wenn ich jedoch ein 7-Gänge-Menü koche, nebenher am Telefon bin und meine Brille beschlägt, ist das wesentlich komplexer. Je mehr nebenläufige Vorgänge es gibt, desto schwieriger wird es.“
Das Kronjuwel für Kyrill im Forschungsfeld der verteilten Algorithmen: Man kann mathematisch beweisen, dass etwas unmöglich ist. „Wenn zu wenig (fehlerfreie) Kommunikation vorhanden ist, können wir klar die Aussage treffen, dass Consensus keinesfalls zu lösen ist – auch wenn die Strategien noch so schlau sind. Niemand kann das dann schaffen, selbst Einstein nicht.“
Von der Grundlagenforschung zur Praxis
Elegante Algorithmen für komplexe Problemstellungen faszinieren den Forscher sehr. Mit neuen Technologien und Systemen wächst auch das Forschungsfeld der verteilten Algorithmen. Gerade bei Real Time Architectures, wo Kyrill an der Entwicklung der nächsten Generation von smartglasses mitarbeitet, bilden oft viele miteinander kommunizierende Einheiten ein komplexes verteiltes System. „Ich beschäftige mich in diesem Forschungsfeld am liebsten mit fundamentalen und grundlegenden Fragestellungen. In der Praxis werden diese Resultate interessant, wann immer neuartige, fehlertolerante verteilte Systeme gebraucht werden. Insbesondere bei der Entwicklung moderner Embedded Systems trifft man heute vielerorts auf genau diese Arten von Fragestellungen. Das beginnt beim Design komplexer System on Chip (SoC) Architekturen, die aus zahlreichen, miteinander verbundenen, autarken Komponenten bestehen und führt über Sensornetzwerke, sowie vernetzte, heterogene cyber-physikalische Systeme bis hin zu kollaborierenden Systems of Systems.“
Zur Person
Kyrill Winkler hat an der TU Wien Technische Informatik studiert und im Bereich „Verteilte Algorithmen“ promoviert (Advisor: Prof. Ulrich Schmid). Im Rahmen des Doktorats war er drei Monate an der École Polytechnique in Paris tätig. Anschließend hat er zwei Jahre als Postdoc-Forscher gearbeitet (davon ein Jahr an der TU Wien und eines an der Universität Wien). Seit November 2021 ist er Teil von ITK Engineering. Kyrill Winkler hat während seiner Forschungsarbeit über zehn peer-reviewte Artikel in wissenschaftlichen Journalen und Tagungsbänden publiziert und führt dies nun in seiner Freizeit weiter. Er will die Welt nicht nur besser verstehen, sondern auch genießen. Neben seiner Forschungstätigkeit liebt er das Wandern und Laufen in der Natur sowie das Verreisen.
Zur ITK Engineering
Die ITK Engineering bietet maßgeschneiderte Entwicklungs- sowie Beratungsleistungen für Industrieunternehmen und Forschungseinrichtungen in den Bereichen Mobilität, Industrie und Medizintechnik. Die Performance-Optimierung von Embedded Systems ist der Schwerpunkt des ITK Engineering-Teams in Österreich. Dafür muss man das System und die Software verstehen, wie auch die Algorithmen dahinter.
