Résumé | We present a distributed algorithm for electing deterministically
a leader in a general network where each processor has a unique
identifier of size O(log n) (n is the number of nodes in the
network). It elects a leader in O(D+log n) rounds (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 improves the best known
algorithm whose bit complexity is O(Dlog n).
In fact, using a lower bound by Kutten et al. and a result of
Dinitz and Solomon, we show that the bit complexity of our algorithm
is optimal (up to a multiplicative constant). Furthermore, this
algorithm requires no knowledge on the graph, such as n or D.
(Travail en collaboration avec A. Casteigts, J. M. Robson et A. Zemmari) |