
Stéphane Devismes, David Ilcinkas, Colette Johnen, Frédéric Mazoit ont obtenu le prix du meilleur papier à Algotel 2025 pour leur article intitulé : « Temps, travail, espace : pourquoi choisir ? Un unisson autostabilisant et ses retombées ».
Dans beaucoup de réseaux, chaque processus possède une horloge logique qu'il incrémente à chaque pas de calcul. Une façon de synchroniser les différents processus consiste alors à exiger que les horloges de deux voisins diffèrent d'au plus un « tic ». Dans ce cas, les horloges sont à l'unisson.
Par ailleurs, suite à des erreurs, les variables internes des processus peuvent être corrompues. Un algorithme est autostabilisant s'il arrive toujours à retrouver un comportement correct à partir d'une telle situation, par exemple resynchroniser les horloges dans le cas de l'unisson.
Cet article d'AlgoTel, dont une version plus longue a été publiée à STACS 2025, présente un algorithme autostabilisant pour le problème de l'unisson asynchrone qui fonctionne dans un modèle faible et qui est à la fois efficace en temps, en charge de travail et en espace. En outre, cet algorithme peut être utilisé pour simuler efficacement des algorithmes synchrones autostabilisants dans des environnements asynchrones, et permet ainsi d'obtenir de nouveaux algorithmes autostabilisants asynchrones meilleurs que toutes les solutions existantes de la littérature pour de nombreux problèmes.
Lire l’article, ici.