Approximating the Size of a Dynamically Growing Asynchronous Distributed Network.

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Apr 01, 1987
Accession Number
ADA187011

Entities

People

  • Baruch Awerbuch
  • Serge A. Plotkin

Organizations

  • Massachusetts Institute of Technology

Tags

Communities of Interest

  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Air Force
  • Algorithms
  • Communication Networks
  • Computer Science
  • Computers
  • Contracts
  • Department Of Defense
  • Detection
  • Distributed Computing
  • Elections
  • Information Processing
  • Information Systems
  • Language
  • Military Research
  • Networks
  • Security
  • Technical Information Centers

Fields of Study

  • Computer science

Readers

  • Graph Algorithms and Convex Optimization.
  • Radio communications and signal processing.
  • Statistical inference.