Direction de recherche : Mesaac MAKPANGOU

Co-encadrement : LEJEUNE Jonathan, SOPENA Julien

Multi-consensus distribué : agrégation et révocabilité

OMAHA (Opportunistic Message Aggregation for pHase-based Algorithms) est un mécanisme d’agrégation de messages conçu pour les algorithmes à phases, couramment utilisés dans les environnements Cloud. Dans ces environnements où la bande passante est une ressource critique, la gestion des petits messages, qui occupent une grande partie du trafic réseau, pose un défi majeur. OMAHA tire parti des communications prévisibles des algorithmes à phases pour regrouper opportunément les messages destinés au même processus, réduisant ainsi le nombre total de messages envoyés. Les expérimentations montrent qu’OMAHA permet d’économiser jusqu’à 30% de bande passante avec une dégradation de latence limitée à 5% sur l’algorithme Paxos.
Dans les systèmes distribués, atteindre un consensus sur une action ou une valeur est un défi complexe, surtout lorsque les processus sont soumis à des contraintes. De nombreux systèmes, tels que les systèmes multi-agents (véhicules autonomes, gestion d’agenda, robotique, etc.) ou encore les systèmes d’allocation de ressources, doivent respecter des contraintes tout en atteignant un objectif global commun. Cependant, les algorithmes de consensus traditionnels ne prennent pas en compte ces contraintes. Pour tolérer les pannes, certains algorithmes définissent un nombre maximal de fautes qu’ils peuvent supporter. Cela permet à l’algorithme de progresser sans attendre la réponse de tous les processus. En conséquence, la valeur décidée est souvent imposée par un sous-ensemble de processus, la majorité. Les contraintes de la minorité sont ainsi ignorées. Pour répondre à ce problème, nous avons introduit le Consensus f-Révocable. Ce consensus revisité permet de choisir une valeur qui respecte les contraintes des processus tout en offrant la possibilité de révoquer une décision prise par la majorité si celle-ci viole les contraintes d’un processus de la minorité.

Publications 2021-2024

• 2024
  • C. Mahamdi : “Multi-consensus distribué : agrégation et révocabilité”, soutenance de thèse, soutenance 02/12/2024, direction de recherche Makpangou, Mesaac, co-encadrement : Lejeune, Jonathan, Sopena, Julien (2024)
• 2023
  • C. Mahamdi, J. Lejeune, J. Sopena, P. Sens, M. Makpangou : “OMAHA: Opportunistic Message Aggregation for pHase-based Algorithms”, 2023 IEEE 28^th Pacific Rim International Symposium on Dependable Computing (PRDC), Singapour, Singapore, pp. 150-160, (IEEE Computer Society), (ISBN: 979-8-3503-5876-6) (2023)
• 2021
  • C. Mahamdi, J. Lejeune, J. Sopena, P. Sens, M. Makpangou : “Réduire le coût de communication des algorithmes à phases par l’agrégation de messages : application à Paxos”, COMPAS 2021 - Conférence francophone d'informatique en Parallélisme, Architecture et Système, Lyon (virtuelle), France (2021)