ACCUEIL

Consignes aux
auteurs et coordonnateurs
Nos règles d'éthique
Auteurs : soumettez
votre article en ligne
Autres revues >>

Technique et Science Informatiques

0752-4072
Revue des sciences et technologies de l'information
 

 ARTICLE VOL 21/5 - 2002  - pp.735-756
TITRE
Protocole universel auto-stabilisant de synchronisation d'horloges de phases

RÉSUMÉ
Nous proposons dans cet article un algorithme uniforme et auto-stabilisant de synchronisation d’horloges de phases ayant K valeurs distinctes, sur des réseaux à topologie d’arbre. Ce protocole est auto-stabilisant parce qu’il garantit qu’en un temps fini tous les processeurs auront la même valeur d’horloge et l’incrémenteront simultanément. Il nécessite (Degu+1)K états par processeur u, où Degu est le degré de u, i.e. le nombre de voisins du processeur u. Le temps de stabilisation est au plus D, où D est le diamètre de l’arbre, ce qui fait de ce protocole de synchronisation le plus rapide sur réseaux à mémoire bornée. Il faut aussi noter que ce protocole est le premier protocole universel (qui fonctionne pour tout K), dont le temps de stabilisation est indépendant de K.

ABSTRACT
In this paper, we propose a self-stabilizing K-phase clock protocol which works on uniform tree networks (i.e. without any root). The protocol is self-stabilizing because it guarantees that all clock value variables will eventually be synchronized and advance in the same value, no matter what the initial state is. It requires (Degu +1)K states by processor u, where Degu is the degree of u; i.e., the number of neighbors that Processor u has. The worst case stabilization time is D, where D is the diameter of the tree. This is the first universal protocol (i.e working for any K), whose stabilization time does not depend on K. Moreover, it is the fastest of all the phase clock protocols with bounded memory.

AUTEUR(S)
Florent NOLOT, Vincent VILLAIN

MOTS-CLÉS
auto-stabilisation, synchronisation d’horloges de phase, systèmes distribués, tolérance aux pannes.

KEYWORDS
clock synchronization, distributed systems, fault-tolerance, self-stabilization.

LANGUE DE L'ARTICLE
Français

 PRIX
• Abonné (hors accès direct) : 12.5 €
• Non abonné : 25.0 €
|
|
--> Tous les articles sont dans un format PDF protégé par tatouage 
   
ACCÉDER A L'ARTICLE COMPLET  (592 Ko)



Mot de passe oublié ?

ABONNEZ-VOUS !

CONTACTS
Comité de
rédaction
Conditions
générales de vente

 English version >> 
Lavoisier