Distributed algorithms for connectivity problem of networks with faulty elements

✍ Scribed by Koichi Wada; Yukio Moritani; Kimio Kawaguchi; Masahiro Morishita

• Book ID: 104591509
• Publisher: John Wiley and Sons
• Year: 1992
• Tongue: English
• Weight: 919 KB
• Volume: 23
• Category: Article
• ISSN: 0882-1666
• DOI: 10.1002/scj.4690230702

✦ Synopsis

Abstract

Distributed algorithms for computing the connectivity of an asynchronous computer network with faulty computers and links are investigated. Computers which are adjacent to faulty computers and links are assumed to be capable of detecting the faults. The existence and efficiency of distributed algorithms depend on the kinds of information each computer is allowed to have on the network before executing an algorithm.

Here, the case in which computers fail and the case in which only links fail are considered separately. It is shown that in the former case there is no algorithm for computing the connectivity regardless of the kind of information a computer has about the network. In the latter case the existence of a distributed algorithm, upper and lower bounds of communication complexity and ideal time complexity are discussed for the following three cases: each computer has only the basic information (its identifier and the number of links connected to it); each computer has the basic information and the identifier of the adjacent computers; and each computer has the basic information and the size of the network.