SQUARE: Scalable Quorum-Based Atomic Memory with Local Reconfiguration

Emmanuelle Anceaume 1 Vincent Gramoli 1, 2 Antonino Virgillito 3
1 ADEPT - Algorithms for Dynamic Dependable Systems
IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires, INRIA Rennes
2 ASAP - As Scalable As Possible: foundations of large scale dynamic distributed systems
Inria Rennes – Bretagne Atlantique , IRISA-D1 - SYSTÈMES LARGE ÉCHELLE
Résumé : Internet applications require more and more resources to satisfy the unpredictable clients needs. Specifically, such applications must ensure quality of service despite bursts of load. Distributed dynamic self-organized systems present an inherent adaptiveness that can face unpredictable bursts of load. Nevertheless quality of service, and more particularly data consistency, remains hardly achievable in such systems since participants (i.e., nodes) can crash, leave, and join the system at arbitrary time. The atomic consistency guarantees that any read operation returns the last written value of a data and is generalizable to data composition. To guarantee atomicity in message-passing model, mutually intersecting sets (a.k.a.quorums) of nodes are used. The solution presented here, namely SQUARE, provides scalability, load-balancing, fault-tolerance, and self-adaptiveness, while ensuring atomic consistency. We specify our solution, prove it correct and analyse it through simulations. \\ Les applications utilisées via internet nécessitent de plus en plus de ressources afin de satisfaire les besoins imprévisibles des clients. De telles applications doivent assurer une certaine qualité de service en dépit des pics de charge. Les systèmes distribués dynamiques capable de s'auto-organiser ont une capacité intrinsèque pour supporter ces pics de charge imprévisibles. Cependant, la qualité de service et plus particulièrement la cohérence des données reste très difficile à assurer dans de tels systèmes. En effet, les participants, ou noeuds, peuvent rejoindre, quitter le système, et tomber en panne de façon arbitraire. La cohérence atomique assure que toute lecture renvoie la dernière valeur écrite et la relation de composition la préserve. Afin de garantir l'atomicité dans un modèle à passage de message, des ensembles de noeuds s'intersectant mutuellement (les quorums) sont utilisés. La solution présentée ici, appelée SQUARE, est exploitable à grande échelle, permet de balancer la charge, tolère les pannes et s'auto-adapte tout en assurant l'atomicité. Nous spécifions la solution, la prouvons correcte et la simulons pour en analyser les performances.
Type de document :
Rapport
[Research Report] PI 1805, 2006, pp.39
Liste complète des métadonnées

https://hal.inria.fr/inria-00082274
Contributeur : Anne Jaigu <>
Soumis le : lundi 3 juillet 2006 - 10:50:01
Dernière modification le : mercredi 16 mai 2018 - 11:23:13
Document(s) archivé(s) le : lundi 20 septembre 2010 - 15:42:50

Fichiers

Identifiants

  • HAL Id : inria-00082274, version 2

Citation

Emmanuelle Anceaume, Vincent Gramoli, Antonino Virgillito. SQUARE: Scalable Quorum-Based Atomic Memory with Local Reconfiguration. [Research Report] PI 1805, 2006, pp.39. 〈inria-00082274v2〉

Partager

Métriques

Consultations de la notice

336

Téléchargements de fichiers

3720