Self-stabilizing wormhole routing

Parallel and distributed systems are composed of individual processors that communicate with one another by exchanging messages through communication links. When the sender and the receiver of a message are not direct neighbors, intermediate processors must cooperate to ensure proper routing.; Wormhole routing is most common in parallel architectures in which messages are sent in small fragments called flits. We assume that each processor will contain a single fixed-size flit buffer for each incoming link. A processor must forward the flit in a given link buffer to another processor before receiving another flit on that link. This permits messages to wind through the entire network from source to destination, resembling a worm. Wormhole routing is a lightweight and efficient method of routing messages between parallel processors.; Our purpose is to modify existing wormhole routing algorithms in familiar topologies to make them self-stabilizing. Self-stabilization is a technique that guarantees tolerance to transient faults (e.g. memory corruption or communication hazard) for a given protocol. Transient faults would typically place the network in an illegitimate state, while Self-stabilization guarantees that the network recovers a correct behavior in finite time, without the need for human intervention. Self-stabilization also guarantees the safety property, meaning that once the network is in a legitimate state, it will remain there until another fault occurs.; This paper presents self-stabilizing network algorithms in the wormhole routing model, using the unidirectional ring and the two-dimensional mesh topologies. We chose the ring topology to illustrate the numerous difficulties of self-stabilization in a wormhole routing environment, even in one of the most simple network topologies. We then extend the results of the ring topology to a more complex two-dimensional mesh network.