| Issue |
RAIRO-Theor. Inf. Appl.
Volume 51, Number 2, April-June 2017
|
|
|---|---|---|
| Page(s) | 51 - 70 | |
| DOI | https://doi.org/10.1051/ita/2017007 | |
| Published online | 13 October 2017 | |
Maintenance of a Spanning Tree For Dynamic Graphs by Mobile Agents and Local Computations
1 ReDCAD, University of Sfax, FSEGS 3018 Sfax, Tunis.
mouna.ktari@redcad.org
2 Information technology department, Taif University, Saoudi Arabia.
haddar.amine@gmail.com
3 LaBRI, CNRS, Bordeaux INP, University of Bordeaux, 33405 Talence, France.
mohamed.mosbah@labri.fr
4 ReDCAD, University of Sfax, FSEGS 3018 Sfax, Tunis.
ahmed.hadjkacem@fsegs.rnu.tn
Received: 13 May 2016
Accepted: 10 July 2017
The problem of constructing and maintaining a spanning tree in dynamic networks is important in distributed systems. Trees are essential structures in various communication protocols such as information broadcasting, routing, etc. In a distributed computing environment, the solution of this problem has many practical motivations. To make designing distributed algorithm easier, we model this latter with a local computation model. Based on the mobile agent paradigm, we present in this paper a distributed algorithm that maintain a hierarchical spanning tree in dynamic networks. We study all topological events that may affect the structure of the spanning tree: we address the appearance and the disappearance of places and communication channels.
Mathematics Subject Classification: 68.00
Key words: Dynamic networks / distributed algorithms / mobile agents / local computation models / spanning tree
© EDP Sciences 2017
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.