Groupe de recherche

Algorithmes pour systèmes simultanés et distribués

Le laboratoire recherche des algorithmes pour les systèmes simultanés (multi-cœurs) et distribués (en réseau à grande échelle). Nous nous concentrons sur l'étude des principes fondamentaux de ces systèmes, ainsi que sur la compréhension des limites inférieures de la complexité et de la calculabilité.

Projets de recherche actuels :

  • Systèmes simultanés :

    • Structures de données simultanées tenant compte de la distribution (avec Dan Alistarh, IST Autria).
      La charge d'une structure de données clé-valeur est faussée lorsque certaines clés sont demandées plus fréquemment que d'autres. Dans un cadre séquentiel, nous utilisons généralement des structures de données auto-ajustables en fonction de la distribution, comme les arbres splay. Peut-on appliquer ce principe dans un système simultané ? 
    • Structures de données simultanées de requête d'intervalle (avec Dan Alistarh, IST Autria).
      Les requêtes classiques de base de données sont l'insertion, la suppression et la vérification du contenu. Mais on peut aussi penser à des requêtes d'intervalle, c'est-à-dire compter le nombre d'éléments dont les clés se trouvent dans un intervalle donné. Comment de telles requêtes d'intervalle peuvent-elles être implémentées dans un cadre simultané ? Et quels sont les coûts inhérents à ces implémentations ? 
    • Structures de données simultanées respectueuses de la mémoire.
      Le stockage des données partagées dans des intervalles de mémoire conséquents permet d'améliorer les performances grâce à une utilisation optimisée du cache. Nous voulons étudier ce principe de design à un niveau fondamental. À cette fin, nous avons introduit la notion d'implémentations simultanées respectueuses de la mémoire et optimales pour la mémoire et nous étudions leurs limites de performance et de complexité.
    • Complexité de la vérification des structures de données simultanées (avec Danny Hendler, Université Ben-Gurion).
      Les techniques conventionnelles utilisées pour vérifier la correction des structures de données simultanées sont soit expérimentales, soit formelles. Mais que savons-nous de la complexité d'une telle vérification ? Par exemple, est-ce NP-complet ?
    • Structures de données de recherche pilotées par le ML (avec Dan Alistarh, IST Autriche).
      La tendance actuelle des structures de données basées sur des index est d'appliquer le machine learning. L'objectif de ce projet est de rendre ces techniques simultanées.
    • Structures de données parallèles groupées.
      Dans le contexte des structures de données de base, telles que l'arborescence de recherche binaire, l'arborescence de recherche par interpolation ou l'index appris, nous explorons la construction parallèle et l'application parallèle de groupes d'opérations.
  • Systèmes distribués :

    • Réseaux auto-ajustables (avec Stefan Schmid, U de Vienne).
      Nous essayons de développer la théorie des réseaux auto-ajustables dans différents modèles pratiques.
    • Partitionnement cohérent par rapport au classement.
      Supposons qu'une base de données stocke une collection de clés sur des partitions, et que leur quantité peut changer dans le temps. La tâche habituelle consiste à redistribuer efficacement les clés entre les partitions en cas d'ajout ou de retrait. Il existe de nombreuses solutions bien connues pour les ensembles non ordonnés de clés, par exemple, le hachage cohérent et le hachage Rendezvous. Cependant, ces approches présentent un inconvénient majeur : les clés sont stockées sur des partitions sans aucun respect de l'ordre des clés, et si nous voulons exécuter une demande de plage (par exemple, GetAllKeys(MinKey, MaxKey)), nous devons interroger chaque partition. Notre approche doit respecter l'ordre et être aussi efficace que possible.
    • Services répliqués dynamiques, reconfigurables et responsables.
      Le principal défi des services répliqués tolérants aux défauts, et des blockchains en particulier, est d'implémenter un accès fiable aux données partagées dans des systèmes où règne une méfiance mutuelle. Les participants au système peuvent avoir des intérêts contradictoires et peuvent même être prêts à tricher, mais l'implémentation doit garantir qu'ils partagent des données et échangent des ressources d'une manière cohérente, accessible et équitable. Telles qu'elles ont été conçues à l'origine, les blockchains résolvent un problème très difficile dans un modèle très difficile. Sans surprise, les solutions existantes sont notoirement lentes et inefficaces. L'objectif de ce projet est de découvrir de nouvelles implémentations efficaces du partage des données en considérant des variantes plus faibles mais néanmoins pratiques du problème, et des variantes plus fortes mais plus réalistes du modèle.

Ces projets sont actuellement menés par les étudiants suivants : Alexandra Drozdova, Ilya Kokorin, Evgeny Feder, Daniil Bolotov, Roman Smirnov, Pavel Ponomarev, Oleg Fafurin, Ildar Amirov (ITMO), Natalia Murashkina (HSE), Alena Martsenuyk, Ildar Zinatullin et Vitalii Krasnov (MIPT).

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

Si vous êtes intéressé par une collaboration, n'hésitez pas à nous contacter.

Membres du groupe

Vitaly Aksenov
Vitaly Aksenov
Chef de laboratoire/groupe de recherche
Aleksandra Drozdova
Aleksandra Drozdova
Chercheur
Petr Kuznetsov
Petr Kuznetsov
Chef de laboratoire/groupe de recherche
Ilya Kokorin
Ilya Kokorin
Chercheur