A General Lower Bound for Electing a Leader in a Ring.
Interim research rept.,
MASSACHUSETTS INST OF TECH CAMBRIDGE LAB FOR COMPUTER SCIENCE
Pagination or Media Count:
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.
- Theoretical Mathematics