Skip to Main content Skip to Navigation
Reports

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
IRISA-D1 - SYSTÈMES LARGE ÉCHELLE, Inria Rennes – Bretagne Atlantique
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.
Complete list of metadata

https://hal.inria.fr/inria-00082274
Contributor : Anne Jaigu <>
Submitted on : Monday, July 3, 2006 - 10:50:01 AM
Last modification on : Thursday, February 11, 2021 - 2:48:04 PM
Long-term archiving on: : Monday, September 20, 2010 - 3:42:50 PM

Identifiers

  • 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⟩

Share

Metrics

Record views

396

Files downloads

3814