A snap-stabilizing point-to-point communication protocol in message-switched networks

A snap-stabilizing protocol, starting from any configuration, always behaves according to its specification. In this paper, we present a snap-stabilizing protocol to solve the 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 informations given by a routing algorithm. By the context of stabilization (in particular, the system starts in any configuration), these informations can be corrupted. So, the existence of a snap-stabilizing protocol for the message forwarding problem implies that we can ask the system to begin forwarding messages even if routing informations are initially corrupted. In this paper, we propose a snap-stabilizing algorithm (in the state model) for the following specification of the problem: Any message can be generated in a finite time. Any emitted message will be delivered to its destination once and only once in a finite time. This implies that our protocol can deliver any emitted message regardless of the state of routing tables in the initial configuration.