Forschungsgruppe

Algorithmen für nebenläufige und verteilte Systeme

Das Labor erforscht Algorithmen für nebenläufige (Mehrkern-) und verteilte (großflächig vernetzte) Systeme. Unser Fokus liegt auf der Erforschung der grundlegenden Prinzipien hinter diesen Systemen und dem Verständnis von Komplexitätsuntergrenzen und Berechenbarkeit.

Aktuelle Forschungsprojekte:

  • Nebenläufige Systeme:

    • Verteilungsbewusste nebenläufige Datenstrukturen (mit Dan Alistarh, IST Österreich).
      Die Last auf einer Schlüssel-Wert-Datenstruktur ist verzerrt, wenn einige Schlüssel häufiger angefordert werden als andere. In einer sequenziellen Umgebung verwenden wir typischerweise einige verteilungsbewusste, selbstanpassende Datenstrukturen, wie z.B. Splay-Bäume. Können wir dieses Prinzip auch in einem nebenläufigen System anwenden? 
    • Nebenläufige Datenstrukturen mit Bereichsabfragen (mit Dan Alistarh, IST Österreich).
      Konventionelle Datenbankabfragen sind Einfügung, Löschung und Überprüfung des Einschlusses. Wir können aber auch an Bereichsabfragen denken, d.h. an das Zählen der Anzahl von Elementen, deren Schlüssel innerhalb eines gegebenen Bereichs liegen. Wie können solche Bereichsabfragen in einer nebenläufigen Umgebung implementiert werden, und welche Kosten sind mit diesen Implementierungen verbunden? 
    • Speicherfreundliche nebenläufige Datenstrukturen.
      Die Speicherung gemeinsam genutzter Daten in konsequenten Speicherbereichen führt zu einer verbesserten Leistung aufgrund einer optimierten Cache-Nutzung. Wir wollen dieses Entwurfsprinzip auf einer fundamentalen Ebene untersuchen. Zu diesem Zweck haben wir den Begriff der speicherfreundlichen und speicheroptimalen nebenläufigen Implementierungen eingeführt und untersuchen deren Leistungs- und Komplexitätsgrenzen.
    • Komplexität der Verifikation von nebenläufigen Datenstrukturen (mit Danny Hendler, Ben-Gurion Universität).
      Konventionelle Methoden zur Verifikation der Korrektheit von nebenläufigen Datenstrukturen sind entweder experimentell oder formal. Aber wissen wir etwas über die Komplexität einer solchen Verifikation? Ist sie zum Beispiel NP-vollständig?
    • ML-gesteuerte Suchdatenstrukturen (mit Dan Alistarh, IST Österreich).
      Der aktuelle Trend bei indexbasierten Datenstrukturen ist die Anwendung von Machine Learning. Das Ziel dieses Projekts ist es, diese Methoden nebenläufig zu machen.
    • Parallele gestapelte Datenstrukturen.
      Im Zusammenhang mit grundlegenden Datenstrukturen wie dem binären Suchbaum, dem Interpolationssuchbaum, dem gelernten Index usw. erforschen wir die parallele Konstruktion und parallele Anwendung von gestapelten Operationen.
  • Verteilte Systeme:

    • Selbstanpassende Netzwerke (mit Stefan Schmid, Uni Wien).
      Wir versuchen, die Theorie der selbstanpassenden Netzwerke in verschiedenen praktischen Modellen zu entwickeln.
    • Konsistente Fragmentierung bezüglich der Reihenfolge.
      Nehmen wir an, eine Datenbank speichert eine Sammlung von Schlüsseln auf Fragmenten (Shards), und deren Anzahl kann sich mit der Zeit ändern. Die typische Aufgabe besteht darin, Schlüssel im Falle ihres Hinzufügens/Entfernens effizient zwischen Fragmenten umzuverteilen. Es gibt viele bekannte Lösungen für ungeordnete Reihen von Schlüsseln, z.B. konsistentes und Rendezvous-Hashing. Diese Ansätze haben jedoch einen großen Nachteil: Die Schlüssel werden auf Fragmenten ohne Berücksichtigung der Reihenfolge der Schlüssel gespeichert, und wenn wir eine Bereichsabfrage durchführen wollen (z.B. GetAllKeys(MinKey, MaxKey)), müssen wir jedes Fragment abfragen. Unser Ansatz muss die Reihenfolge respektieren und so effizient wie möglich sein.
    • Dynamische, rekonfigurierbare und verlässliche replizierte Dienste.
      Die größte Herausforderung bei fehlertoleranten replizierten Diensten und insbesondere bei Blockchains ist die Implementierung eines vertrauenswürdigen Zugriffs auf gemeinsame Daten in Systemen mit gegenseitigem Misstrauen. Systemteilnehmer können widersprüchliche Interessen haben und sogar bereit sein, zu betrügen, aber von der Implementierung wird erwartet, dass sie Daten gemeinsam nutzen und Assets auf konsistente, verfügbare und faire Weise austauschen. So wie sie ursprünglich konzipiert wurden, lösen Blockchains ein sehr schwieriges Problem in einem sehr schwierigen Modell. Nicht überraschend ist, dass bestehende Lösungen notorisch langsam und ineffizient sind. Das Ziel dieses Projekts ist es, neuartige und effiziente Implementierungen für die gemeinsame Nutzung von Daten zu entdecken, indem schwächere, aber dennoch praktikable Varianten des Problems und stärkere, aber realistischere Varianten des Modells betrachtet werden.

Diese Projekte werden derzeit von den folgenden Studierenden durchgeführt: Alexandra Drozdova, Ilya Kokorin, Evgeny Feder, Daniil Bolotov, Roman Smirnov, Pavel Ponomarev, Oleg Fafurin, Ildar Amirov (ITMO), Natalia Murashkina (HSE), Alena Martsenuyk, Ildar Zinatullin, Vitalii Krasnov (MIPT).

Kontakt: Vitaly Aksenov, aksenov.vitaly@gmail.com.

Wenn Sie an einer Zusammenarbeit interessiert sind, nehmen Sie bitte Kontakt mit uns auf.

Gruppenmitglieder

Vitaly Aksenov
Vitaly Aksenov
Leiter*in Forschungslabor/-gruppe
Aleksandra Drozdova
Aleksandra Drozdova
Forscher*in
Petr Kuznetsov
Petr Kuznetsov
Leiter*in Forschungslabor/-gruppe
Ilya Kokorin
Ilya Kokorin
Forscher*in