Structured Distributed Computation under Communication and Computation Constraints

Calcul distribué structuré sous des contraintes de communication et de calcul Le calcul distribué constitue aujourd'hui un élément central des systèmes modernes de communication et de traitement de données, soutenant des applications à grande échelle telles que les réseaux sans fil, l'apprentissage automatique ou encore le traitement en temps réel. Dans ce contexte, un enjeu fondamental réside dans la maîtrise du compromis entre les coûts de calcul et de communication, en particulier dans des environnements multi-utilisateurs. Cette thèse propose une étude approfondie de ce compromis à travers trois approches complémentaires, chacune mettant en évidence un aspect structurel spécifique des tâches de calcul distribuées. Dans un premier axe, nous analysons le rôle de l'influence des données dans le calcul distribué de fonctions booléennes. En adoptant une approche fondée sur la sensibilité, nous montrons que le placement des données d'entrée sur les serveurs joue un rôle déterminant dans les coûts globaux du système. En nous appuyant sur des outils issus de l'analyse des fonctions booléennes, nous établissons des bornes théoriques et proposons des schémas d'allocation permettant de privilégier les variables les plus influentes, réduisant ainsi les redondances de calcul et les charges de communication. Dans un second axe, nous nous intéressons au calcul distribué de fonctions non linéairement séparables à travers un cadre de factorisation tensorielle creuse. Les demandes des utilisateurs y sont modélisées sous forme de tenseurs de grande dimension, capturant des interactions complexes entre variables. Nous développons des schémas réalisables reposant sur des décompositions tensorielles à support fixe et des structures de pavage multidimensionnel, complétés par des méthodes combinatoires d'affectation visant à éliminer les redondances entre serveurs. Cette approche permet de réduire significativement le nombre de serveurs requis par rapport aux méthodes classiques basées sur la factorisation matricielle, soulignant l'intérêt d'exploiter la structure multidimensionnelle des problèmes. Dans un troisième axe, nous étudions la multiplication matricielle distribuée dans des environnements dynamiques soumis à des contraintes de latence (stragglers) et de confidentialité, notamment dans le contexte des réseaux véhiculaires. Nous proposons un schéma original de calcul distribué codé combinant le codage de source de Körner--Marton avec des techniques basées sur des codes polynomiaux. Le cadre obtenu assure à la fois une robustesse face aux serveurs lents et une protection contre les fuites d'information, permettant ainsi un calcul distribué à la fois efficace et sécurisé. Dans son ensemble, cette thèse met en évidence des liens nouveaux entre le calcul distribué, l'analyse des fonctions booléennes, les méthodes tensorielles et la théorie de l'information. Les contributions proposées apportent à la fois des éclairages théoriques et des outils méthodologiques pour la conception de systèmes distribués performants, évolutifs et robustes.