A General Lower Bound for Electing a Leader in a Ring.

Abstract

A lower bound of omega(n log n) messages is proved, for the problem of electing a leader in a ring of n processors. Unlike in previous work, the value of n is arbitrary, and not constrained to be a power of 2. The result is proved for comparison algorithms, but previously known techniques using Ramsey's theorem show that the result applies to other types of algorithms as well. Keywords: Leader election; distributed algorithms; lower bounds; synchronous algorithms, message complexity and symmetry.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Mar 01, 1985
Accession Number
ADA156241

Entities

People

  • G. N. Frederickson
  • N. A. Lynch

Organizations

  • Massachusetts Institute of Technology

Tags

Communities of Interest

  • C4I
  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Algorithms
  • Computer Science
  • Computers
  • Contracts
  • Elections
  • Information Processing
  • Information Systems
  • Language
  • Massachusetts
  • Military Research
  • Programming Languages
  • Sequences
  • Symmetry
  • Technical Information Centers
  • Universities

Readers

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