Accession Number : ADA187011

Title :   Approximating the Size of a Dynamically Growing Asynchronous Distributed Network.

Descriptive Note : Technical rept.,

Corporate Author : MASSACHUSETTS INST OF TECH CAMBRIDGE LAB FOR COMPUTER SCIENCE

Personal Author(s) : Awerbuch, Baruch ; Plotkin, Serge A

PDF Url : ADA187011

Report Date : Apr 1987

Pagination or Media Count : 20

Abstract : We show how to approximate up to a constant factor the size of a dynamically growing asynchronous distributed network. The technique presented in this paper has an amortized message complexity of 0(log2 V) per node, where V is the final size of the network. This technique appears to be useful primitive in constructing distributed algorithms. In this paper we show how to apply this technique to construct an efficient distributed algorithm for leader election in a faulty network. The algorithm has a message complexity 0( E + V log 2 V), which is in an improvement of 0 (log 2 V) over the previously known algorithms. Keywords: Termination detection, Leader election, Distributed networks.

Descriptors :   *NETWORK ANALYSIS(MANAGEMENT), *COMMUNICATIONS NETWORKS, ALGORITHMS, ASYNCHRONOUS SYSTEMS, DETECTION, DISTRIBUTION, EFFICIENCY, SIZES(DIMENSIONS), COUNTING METHODS

Subject Categories : Computer Systems

Distribution Statement : APPROVED FOR PUBLIC RELEASE