Computing and updating the process number in trees

David Coudert 1 Florian Huc 1 Dorian Mazauric 1
1 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : The process number is the minimum number of requests that have to be simultaneously disturbed during a routing reconfiguration phase of a connection oriented network. From a graph theory point of view, it is similar to the node search number, and thus to the pathwidth, however they are not always equal. In general determining these parameters is NP-complete. We present a distributed algorithm to compute these parameters and the edge search number, in trees. It can be executed in an asynchronous environment, requires n steps, an overall computation time of O(n log n), and n messages of size log3 n + 2. Then, we propose a distributed algorithm to update these parameters on each component of a forest after addition or deletion of any tree edge. This second algorithm requires O(D) steps, an overall computation time of O(D log n), and O(D) messages of size log3 n + 3, where D is the diameter of the new connected component.
Type de document :
Communication dans un congrès
Baker, Theodore P. and Bui, Alain and Tixeuil, Sébastien. 12th International Conference On Principles Of DIstributed Systems (OPODIS), Dec 2008, Luxor, Egypt. Springer, 5401, 2008, Lecture Notes in Computer Science. <10.1007/978-3-540-92221-6_37>
Liste complète des métadonnées


https://hal.inria.fr/inria-00429149
Contributeur : David Coudert <>
Soumis le : samedi 31 octobre 2009 - 16:03:20
Dernière modification le : samedi 31 octobre 2009 - 20:51:39
Document(s) archivé(s) le : mardi 16 octobre 2012 - 13:01:55

Fichier

opodis08-nostyle.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

David Coudert, Florian Huc, Dorian Mazauric. Computing and updating the process number in trees. Baker, Theodore P. and Bui, Alain and Tixeuil, Sébastien. 12th International Conference On Principles Of DIstributed Systems (OPODIS), Dec 2008, Luxor, Egypt. Springer, 5401, 2008, Lecture Notes in Computer Science. <10.1007/978-3-540-92221-6_37>. <inria-00429149>

Partager

Métriques

Consultations de
la notice

197

Téléchargements du document

80