Actualités
  Période
semaine
ou mois
aucune période


  Thèmes:
Thèses
Colloques
Autres
Groupes
Tous les thèmes

   
  Liens:
Voir les thèses

Voir les colloques

Voir les autres événements

Voir la page des groupes

Accéder à l'intranet

Intitulé:   
Self-Stabilizing Leader Election in Polynomial Steps
du groupe Algorithmique Distribuée

Date 2015-02-16  14:00-15:00
TitreSelf-Stabilizing Leader Election in Polynomial Steps 
RésuméWe present a silent self-stabilizing leader election algorithm for bidirectional connected identified networks of arbitrary topology. This algorithm is written in the locally shared memory model. It assumes the distributed unfair daemon, the most general scheduling hypothesis of the model. Our algorithm requires no global knowledge on the network (such as an upper bound on the diameter or the number of processes, for example). We show that its stabilization time is in Theta(n^3) steps in the worst case, where n is the number of processes. Its memory requirement is asymptotically optimal, i.e., Theta(log n) bits per processes. Its round complexity is of the same order of magnitude (i.e., Theta(n) rounds), as the best existing algorithm (proposed by Datta et al) designed with similar settings,i.e., it does not use global knowledge and is proven under the unfair daemon). To the best of our knowledge, this is the first asynchronous self-stabilizing leader election algorithm for arbitrary identified networks that is proven to achieve a stabilization time polynomial in steps. By contrast, we show that the previous best existing algorithm designed with similar settings stabilizes in a non polynomial number of steps in the worst case. This talk and Stephane's visit is supported by CPU.  
Lieu178 
OrateurStéphane Devismes 
UrlUniversité Joseph Fourier, Grenoble I 



Aucun document lié à cet événement.

Retour
Retour à l'index