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