Accession Number:

ADA156241

Title:

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

Descriptive Note:

Interim research rept.,

Corporate Author:

MASSACHUSETTS INST OF TECH CAMBRIDGE LAB FOR COMPUTER SCIENCE

Personal Author(s):

Report Date:

1985-03-01

Pagination or Media Count:

19.0

Abstract:

A lower bound of omegan 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 Ramseys 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.

Subject Categories:

  • Theoretical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE