Approximating the Size of a Dynamically Growing Asynchronous Distributed Network

摘要

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.