Evènement pour le groupe Algorithmique Distribuée


Date 2016-03-21  14:00-15:00
TitreDeterministic Leader Election in O(D+log n) Rounds with Messages of size O(1) 
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) 
Lieu178 
OrateurYves Métivier 



Aucun document lié à cet événement.

Retour
Retour à l'index