2009/05/12 by Alain Cournier, Cournier, Alain, Swan Dubois +3
Computer Science · #Distributed #FOS: Computer and information sciences #Parallel #and Cluster Computing (cs.DC) #cs.DC
paper · pdf · doi:10.48550/arxiv.0905.1786
arxiv created 2009/05/12 · arxiv updated 2009/12/01
A snap-stabilizing algorithm ensures that it always behaves according to its specifications whenever it starts from an arbitrary configuration. In this paper, we interest in the message forwarding problem in a message-switched network. We must manage network ressources in order to deliver messages to any processor of the network. In this goal, we need information given by a routing algorithm. But, due to the context of stabilization, this information can be initially corrupted. It is why the existence of snap-stabilizing algorithms for this task (proved in [CDV09]) implies that we can ask the system to begin forwarding messages even if routing tables are initially corrupted. In this paper, we generalize the previous result given a necessary and sufficient condition to solve the forwarding problem in a snap-stabilizing way.