Two absolute bounds for distributed bit complexity

The concept of distributed communication bit complexity was introduced by Dinitz, Rajsbaum, and Moran. They studied the bit complexity of Consensus and Leader Election, arriving at more or less exact bounds. This paper answers two questions on Leader Election, which remained there open. The first is...

Full description

Saved in:
Bibliographic Details
Published in:Theoretical computer science 2007-10, Vol.384 (2), p.168-183
Main Authors: Dinitz, Yefim, Solomon, Noam
Format: Article
Language:English
Subjects:
Absolute bound
Algorithmics. Computability. Computer arithmetics
Applied sciences
Bit complexity
Computer science
control theory
systems
Distributed computing
Exact sciences and technology
Leader election
Miscellaneous
Theoretical computing
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The concept of distributed communication bit complexity was introduced by Dinitz, Rajsbaum, and Moran. They studied the bit complexity of Consensus and Leader Election, arriving at more or less exact bounds. This paper answers two questions on Leader Election, which remained there open. The first is to close the gap between the known upper and lower bounds, for electing a leader by two linked processors. The second is whether the suggested algorithm, sending 1.5 n bits while electing a leader in a chain of even length n , is optimal, in the case when n is known to the processors. For both problems, absolutely exact bounds are found. Moreover, the presented lower bound proofs show that there is no optimal algorithm other than the suggested ones.
ISSN:0304-3975
1879-2294
DOI:10.1016/j.tcs.2007.04.027