1. The First Fully Polynomial Stabilizing Algorithm for BFS Tree Construction
- Author
-
Alain Cournier, Stephane Rovedakis, Vincent Villain, Modélisation, Information et Systèmes - UR UPJV 4290 (MIS), Université de Picardie Jules Verne (UPJV), CEDRIC. Réseaux et Objets Connectés (CEDRIC - ROC), Centre d'études et de recherche en informatique et communications (CEDRIC), Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM)-Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM), ANR-08-SEGI-0025,SPADES,Plateforme de Services Pour Architecture Petascale et DistribuéES.(2008), and Antonio Fernández Anta and Giuseppe Lipari and Matthieu Roy
- Subjects
Polynomial ,K-ary tree ,Computer science ,Breadth-first search ,0102 computer and information sciences ,02 engineering and technology ,Minimum spanning tree ,k-minimum spanning tree ,Distributed systems ,Polynomial algorithm ,01 natural sciences ,Theoretical Computer Science ,Distributed minimum spanning tree ,0202 electrical engineering, electronic engineering, information engineering ,Transient (computer programming) ,ComputingMilieux_MISCELLANEOUS ,Minimum degree spanning tree ,Spanning tree ,020206 networking & telecommunications ,State (functional analysis) ,Spanning tree construction ,Stabilization ,Computer Science Applications ,Fault-tolerance ,Tree (data structure) ,Computational Theory and Mathematics ,010201 computation theory & mathematics ,020201 artificial intelligence & image processing ,Mutual exclusion ,Routing (electronic design automation) ,[INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC] ,Algorithm ,Information Systems - Abstract
The construction of a spanning tree is a fundamental task in distributed systems which allows to resolve other tasks (i.e., routing, mutual exclusion, network reset). In this paper, we are interested in the problem of constructing a Breadth First Search (BFS) tree. Stabilization is a versatile technique which ensures that the system recover a correct behavior from an arbitrary global state resulting from transient faults. A fully polynomial algorithm has a round complexity in O(da) and a step complexity in O(nb) where d and n are the diameter and the number of nodes of the network and a and b are constants. We present the first fully polynomial stabilizing algorithm constructing a BFS tree under a distributed daemon. Moreover, as far as we know, it is also the first fully polynomial stabilizing algorithm for spanning tree construction. Its round complexity is in O(d2) and its step complexity is in O(n6). To our knowledge, since in general the diameter of a network is much smaller than the number of nodes (log(n) in average instead of n), this algorithm reaches the best compromise of the literature between the complexities in terms of rounds and in terms of steps.
- Published
- 2019
- Full Text
- View/download PDF