Anzeige
Erschienen in:
2016 | OriginalPaper | Buchkapitel
Deterministic Leader Election in \(O(D+\log n)\) Time with Messages of Size O(1)
verfasst von : Arnaud Casteigts, Yves Métivier, John Michael Robson, Akka Zemmari
Erschienen in: Distributed Computing
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
This paper presents a distributed algorithm, called \(\mathcal{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 round complexity of \(O(D +\log n)\). This substantially improves upon the best known algorithm whose bit round complexity is \(O(D\log n)\). In fact, using the lower bound by Kutten et al. [13] and a result of Dinitz and Solomon [8], we show that the bit round complexity of \(\mathcal{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.