A reconfiguration algorithm for a double-loop token ring local area network

A distributed algorithm to reconfigure a double-loop token-ring local area network following topological changes is presented. Each node, upon detection of a broken link, attempts to use another link, and when this is not possible it connects its input and output lines to form a loopback. The nodes communicate only with their neighbors and base their actions on the messages they receive and on their local observations. The algorithm guarantees that at all times the network is organized to provide maximum possible connectivity among the nodes-either one loop that encompasses all nodes in the network or several subloops, each of which operates as a separate token-ring network. Tokens are generated or eliminated as necessary to result in one and only one token in each (sub)loop. The algorithm is formally specified and its properties are verified