An efficient distributed orientation algorithm (Corresp.)

Abstract

An algorithm for constructing and maintaining full information on the structure of a communication network is presented. The algorithm uses distributed computation. It can be used as an information-gathering step, to be followed by special-purpose algorithms which are to be executed within the nodes, without any additional communication. The load of the lines of the network is measured and shown to be better than any known algorithm for determining connectivity, suggesting shortest path, routing, etc., when the number of topological changes is big enough. It is shown that the network will recover in finite time from a finite number of topological changes in the network. Other, more powerful, recovery criteria are also given.