|
| | | | |
| | | |
| Stat |
Members: 3644
Articles: 2'499'343
Articles rated: 2609
16 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Deterministic Leader Election in $O(D + log n)$ Time with Messages of Size $O(1)$ | | Arnaud Casteigts
; Yves Métivier
; John Michael Robson
; Akka Zemmari
; | | Date: |
6 May 2016 | | Abstract: | This paper presents a distributed algorithm, called STT, for electing
deterministically a leader in an arbitrary network, assuming processors have
unique identifiers of size $O(log n)$, where $n$ is the number of processors.
It elects a leader in $O(D +log n)$ rounds, where $D$ is the diameter of the
network, with messages of size $O(1)$. Thus it has a bit complexity of $O(D
+log n)$. This substantially improves upon the best known algorithm whose bit
complexity is $O(Dlog n)$. In fact, using the lower bound by Kutten et al.
[26] and a result of Dinitz and Solomon [17], we show that the bit complexity
of STT is optimal (up to a constant factor), which is a step forward in
understanding the interplay between time and message optimality for the
election problem. Our algorithm requires no knowledge on the graph such as $n$
or $D$. | | Source: | arXiv, 1605.1903 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser claudebot
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER