2019/07/18 by Ajoy K. Datta, Stéphane Devismes, Datta, Ajoy K. +5
Computer Science · #Advanced Data Storage Technologies #Distributed #Distributed systems and fault tolerance #FOS: Computer and information sciences #Mobile Agent-Based Network Management #Parallel #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.1907.07944
openalex publication_date 2019/07/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We present results on the last topic we collaborate with our late friend, Professor Ajoy Kumar Datta (1958-2019). In this work, we shed new light on a self-stabilizing wave algorithm proposed by Colette Johnen in 1997. This algorithm constructs a BFS spanning tree in any connected rooted network. Nowadays, it is still the best existing self-stabilizing BFS spanning tree construction in terms of memory requirement, \em i.e., it only requires Θ(1) bits per edge. However, it has been proven assuming a weakly fair daemon. Moreover, its stabilization time was unknown. Here, we study the slightly modified version of this algorithm, still keeping the same memory requirement. We prove the self-stabilization of this variant under the distributed unfair daemon and show a stabilization time in O(D.n2) rounds, where D is the network diameter and n the number of processes.