Brief Announcement: Analysis of a Memory-Efficient Self-stabilizing BFS Spanning Tree Construction
Document Type
Article
Publication Date
11-14-2019
Publication Title
Stabilization, Safety, and Security of Distributed Systems - 21st International Symposium, SSS 2019, Pisa, Italy, October 22-25, 2019, Proceedings
Volume
11914
First page number:
99
Last page number:
104
Abstract
We present preliminary results on the last topic we collaborate with our late friend, Professor Ajoy Kumar Datta (1958–2019), who prematurely left us a few months ago. In this work, we shed new light on a self-stabilizing wave algorithm proposed by Colette Johnen in 1997 [12]. 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, 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.
Keywords
Self-Stabilization; BFS Spanning Tree; Distributed Unfair Daemon; Stabilization Time; Round Complexity
Disciplines
Computer Sciences | Physical Sciences and Mathematics
Language
English
Repository Citation
Larmore, L.,
Datta, A.,
Devismes, S.,
Johnen, C.
(2019).
Brief Announcement: Analysis of a Memory-Efficient Self-stabilizing BFS Spanning Tree Construction.
Stabilization, Safety, and Security of Distributed Systems - 21st International Symposium, SSS 2019, Pisa, Italy, October 22-25, 2019, Proceedings, 11914
99-104.