Electing A Leader in a Synchronous Ring. Revision.

Abstract

We consider the problem of electing a leader in a synchronous ring of n processors. We obtain both positive and negative results. On the one hand, if processor ID's are chosen from some countable set, then there is an algorithm which uses only 0(n) messages in the worst case. Alternatively, if the number of rounds is required to be bounded by some t in the worst case, the ID's are chosen from any set having at least f(n,t) elements, for a certain very fast-growing function f, then any algorithm requires omega (n log n ) messages in the worst case. Keywords: Leader election, distributed algorithms, lower bounds, synchronous algorithms, message complexity and symmetry.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jul 01, 1985
Accession Number
ADA161610

Entities

People

  • Greg N. Frederickson
  • Nancy Lynch

Organizations

  • Massachusetts Institute of Technology

Tags

Communities of Interest

  • C4I
  • Energy and Power Technologies
  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Abstracts
  • Algorithms
  • Classification
  • Computations
  • Computer Science
  • Computers
  • Context Free Grammars
  • Contracts
  • Department Of Defense
  • Elections
  • Fish
  • Information Processing
  • Massachusetts
  • Military Research
  • Security
  • Symmetry
  • Universities

Fields of Study

  • Mathematics

Readers

  • Graph Algorithms and Convex Optimization.
  • Parallel and Distributed Computing.