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 31/8-10 - 2012  - pp.1301-1325  - doi:10.3166/tsi.31.1301-1325
TITRE
Évaluation de politiques d’adaptation au risque de collisions dans un consensus de type « Fast Paxos »

TITLE
Evaluation of adaptive strategies to face collisions in a

RÉSUMÉ

Aucune collision ne se produit durant une instance de consensus si toutes les valeurs proposées durant ce consensus sont identiques. Afin de réduire le temps nécessaire à une prise de décision, certains protocoles de consensus anticipent sur le fait qu’aucune collision ne se produira au cours du prochain consensus exécuté. Ce principe de conception a notamment été étudié par Lamport qui a proposé une variante au protocole Paxos, appelée Fast Paxos. En l’absence de collision, un gain de temps est observé. Malheureusement, le fait de déclencher cette optimisation revient à faire un pari sur l’avenir et, en cas de collision non prévue, le coût de la procédure de recouvrement s’avère être bien plus important que le gain initialement escompté. Dans cet article, nous décrivons brièvement le protocole Paxos-MIC qui permet d’exécuter une séquence d’instances de consensus. Après chaque consensus, le choix d’activer l’optimisation risquée durant le prochain consensus est fait localement et dynamiquement en évaluant une condition de déclenchement. Nous étudions différentes conditions de déclenchement et nous évaluons les gains susceptibles d’être obtenus en analysant le comportement du protocole à l’aide d’une trace réelle correspondant à l’activité du site web d’une grande école d’ingénieur durant quinze jours consécutifs.



ABSTRACT

No collision occurs during a consensus instance if all the proposed values are the same. To reduce the time required to reach a decision, some consensus protocols are betting that no collision will occur during the next consensus instance. This idea has been studied by Lamport who proposed a variant of the Paxos protocol called Fast Paxos. When no collision occurs the proposed optimization leads to a gain. Unfortunately this optimization is risky and the triggering of this optimization may lead to an additional cost when the circumstances are unfavorable. In this paper we describe briefly the Paxos-MIC protocol which allows to execute a sequence of consensus instances. After each consensus, a local triggering criterion is evaluated to determine if the risky optimization has to be used or not during the next consensus. We propose different triggering criteria and we analyze their accuracy to predict collisions when proposed values are produced at the rate observed in a real trace. The selected trace contains all the http requests addressed to a real web site during a period of 15 days.



AUTEUR(S)
Izabela MOISE, Michel HURFIN, Jean-Pierre LE NARZUL, Frédéric MAJORCZYK

MOTS-CLÉS
consensus, problèmes d’accord, Paxos

KEYWORDS
consensus, agreement problems, Paxos.

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  (296 Ko)



Mot de passe oublié ?

ABONNEZ-VOUS !

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

 English version >> 
Lavoisier