How to improve snap-stabilizing point-to-point communication space complexity ?

Abstract : A snap-stabilizing protocol, starting from any configuration, always behaves according to its specification. In this paper, we are interested in message forwarding problem in a message-switched network. In this problem, we must manage resources of the system to deliver messages to any processor of the network. In this purpose, we use information given by a routing algorithm. By the context of stabilization (in particular, the system starts in any configuration), this information can be corrupted. In [1], authors show that there exists snap-stabilizing algorithms for this problem (in the state model). That implies that we can ask the system to begin forwarding messages without losses even if routing informations are initially corrupted. In this paper, we propose another snap-stabilizing algorithm for this problem which improves the space complexity of the one of [1].
Type de document :
Communication dans un congrès
SSS 2009 - 11th International Symposium on Stabilization, Safety, and Security of Distributed Systems, Nov 2009, Lyon, France. Springer, 5873, pp.195-208, 2009, Lecture Notes in Computer Science. 〈10.1007/978-3-642-05118-0_14〉
Liste complète des métadonnées

https://hal.inria.fr/inria-00628081
Contributeur : Swan Dubois <>
Soumis le : vendredi 30 septembre 2011 - 13:34:54
Dernière modification le : jeudi 11 janvier 2018 - 06:20:06

Identifiants

Collections

Citation

Alain Cournier, Swan Dubois, Vincent Villain. How to improve snap-stabilizing point-to-point communication space complexity ?. SSS 2009 - 11th International Symposium on Stabilization, Safety, and Security of Distributed Systems, Nov 2009, Lyon, France. Springer, 5873, pp.195-208, 2009, Lecture Notes in Computer Science. 〈10.1007/978-3-642-05118-0_14〉. 〈inria-00628081〉

Partager

Métriques

Consultations de la notice

73