Skip to Main content Skip to Navigation
Conference papers

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].
Complete list of metadata
Contributor : Swan Dubois Connect in order to contact the contributor
Submitted on : Friday, September 30, 2011 - 1:34:54 PM
Last modification on : Friday, August 5, 2022 - 11:22:10 AM

Links full text



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. pp.195-208, ⟨10.1007/978-3-642-05118-0_14⟩. ⟨inria-00628081⟩



Record views