Description
Date depot: 7 septembre 2022
Titre: Modèles de complexité calculatoire dans le nuage
Directeur de thèse:
Charles BOUILLAGUET (LIP6)
Domaine scientifique: Sciences et technologies de l'information et de la communication
Thématique CNRS : Calcul arithmétique et formel, codage et cryptologie
Resumé: La complexité des algorithmes est traditionnellement mesurée en comptant le nombre d’opérations « élémentaires » effectuées dans un modèle de calcul abstrait, qui est une simplification très grossière d’un véritable ordinateur. Par exemple, il est bien connu que le tri fusion nécessite O (n log n) opérations.
Exécuter des calculs dans le nuage, c’est-à-dire en louant des machines virtuelles à l’opérateur d’un nuage public, pose le problème du coût des calculs d’une manière radicalement différente. Le coût est alors proportionnel à la somme des durées des locations des machines virtuelles utilisées.
Des bornes inférieures VLSI des années 1980 impliquent vraissemblablement que trier dans le nuage coûte O(n^1.5), asymptotiquement plus cher que dans le modèle de la Random access Machine.
Dans le modèle de calcul usuel, de nombreux « progrès » algorithmiques consistent à utiliser plus de mémoire pour faire baisser le nombre d’opérations. La question de fond que pose ce sujet de thèse est : dans le nuage ces « progrès » ne sont-ilspas des regressions ? Ne font-ils pas augmenter le coût (en augmentant la quantité de ressources matérielles nécessaires) ?
Doctorant.e: Alharbi Ahmed