
Stéphane Devismes, David Ilcinkas, Colette Johnen and Frédéric Mazoit were awarded the best paper prize at Algotel 2025 for their article entitled: "Time, work, space: why choose? A self-stabilizing unison and its fallout".
In many networks, each process has a logical clock, which it increments with each calculation step. One way of synchronizing the various processes is to require that the clocks of two neighbors differ by no more than one “tick”. In this case, the clocks are in unison.
On the other hand, errors can corrupt internal process variables. An algorithm is self-stabilizing if it can always recover correct behavior from such a situation, e.g. resynchronize the clocks in the case of unison.
This AlgoTel paper, a longer version of which was published at STACS 2025, presents a self-stabilizing algorithm for the asynchronous unison problem that works in a weak model and is efficient in terms of time, workload and space. In addition, this algorithm can be used to efficiently simulate self-stabilizing synchronous algorithms in asynchronous environments, and thus yields new asynchronous self-stabilizing algorithms that are better than any existing solutions in the literature for many problems.
Read the article, here.