A Self-Stabilizing Memory Efficient Algorithm for the Minimum Diameter Spanning Tree under an Omnipotent Daemon

Autor: Fadwa Boubekeur, Lélia Blin, Swan Dubois
Přispěvatelé: Networks and Performance Analysis (NPA), Laboratoire d'Informatique de Paris 6 (LIP6), Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS), Université d'Évry-Val-d'Essonne (UEVE), Large-Scale Distributed Systems and Applications (Regal), Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)-Inria Paris-Rocquencourt, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), Données et algorithmes pour une ville intelligente et durable - DAVID (DAVID), Université de Versailles Saint-Quentin-en-Yvelines (UVSQ), DistributEd aLgorithms and sYStems (DELYS), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-LIP6
Jazyk: angličtina
Rok vydání: 2015
Předmět:
Routing protocol
Polynomial
Theoretical computer science
Computer Networks and Communications
Computer science
0102 computer and information sciences
02 engineering and technology
Minimum spanning tree
01 natural sciences
Theoretical Computer Science
Distributed minimum spanning tree
Center
Diameter
Artificial Intelligence
Kruskal's algorithm
020204 information systems
Convergence (routing)
0202 electrical engineering
electronic engineering
information engineering
[INFO]Computer Science [cs]
Self-stabilization
Spanning tree
Graph
Unfair daemon
010201 computation theory & mathematics
Hardware and Architecture
Metric (mathematics)
Reverse-delete algorithm
MDST
Graph (abstract data type)
Daemon
[INFO.INFO-DC]Computer Science [cs]/Distributed
Parallel
and Cluster Computing [cs.DC]
Algorithm
Software
Zdroj: Parallel and Distributed Processing Symposium (IPDPS), 2015 IEEE International
29rd IEEE International Symposium on Parallel and Distributed Processing (IPDPS 2015)
29rd IEEE International Symposium on Parallel and Distributed Processing (IPDPS 2015), May 2015, Hyberabad, India. pp.1065-1074, ⟨10.1109/IPDPS.2015.44⟩
Journal of Parallel and Distributed Computing
Journal of Parallel and Distributed Computing, Elsevier, 2018, 117, pp.50-62. ⟨10.1016/j.jpdc.2018.02.007⟩
IPDPS
Journal of Parallel and Distributed Computing, 2018, 117, pp.50-62. ⟨10.1016/j.jpdc.2018.02.007⟩
ISSN: 0743-7315
1096-0848
DOI: 10.1109/IPDPS.2015.44⟩
Popis: International audience; The diameter of a network is one of the most fundamental network parameters. Being able to compute the diameter is an important problem in the analysis of large networks, and moreover this parameter has many important practical applications in real networks. As a consequence, it is natural to study this problem in a distributed system, and more specifically in a distributed system tolerant to transient faults. More specifically, we are interested in the problem to identify one of the centers of graph. Once done, we construct a minimum diameter spanning tree rooted in this centre. Of course, the challenging problem is to compute one centre of the graph. We present a uniform self-stabilizing algorithm for the minimum diameter spanning tree construction problem in the state model. Our protocol has several attractive features that makes it suitable for practical purposes. It is the first algorithm for this problem that operates under the unfair adversary (also called unfair daemon). In other words, no restriction is made on the distributed behaviour of the system. Consequently, it is the hardest adversary to deal with. Moreover, our algorithm needs only O(log n) bits of memory per process (where n is the number of processes), that improves the previous result by a factor n. These improvements are not achieved to the detriment of the convergence time, that stays reasonable with O(n2) rounds.
Databáze: OpenAIRE
Externí odkaz: