Skip to Main content Skip to Navigation
Reports

SAM: Self* Atomic Memory for P2P Systems

Emmanuelle Anceaume 1 Maria Gradinariu 1 Vincent Gramoli 1 Antonino Virgillito 1
1 ADEPT - Algorithms for Dynamic Dependable Systems
IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires, INRIA Rennes
Abstract : We propose an implementation of self-adjusting and self-healing atomic memory in highly dynamic systems exploiting peer-to-peer (p2p) techniques. Our approach, named SAM, brings together new and old research areas such as p2p overlays, dynamic quorums and replica control. In SAM, nodes form a connected overlay. To emulate the behavior of an atomic memory we use intersected sets of nodes, namely quorums, where each node hosts a replica of an object. In our approach, a quorum set is obtained by performing a deterministic traversal of the overlay. The SAM overlay features self-* capabilities: that is, the overlay self-heals on the fly when nodes hosting replicas leave the system and the number of active replicas in the overlay dynamically self-adjusts function of the object load. In particular, SAM pushes requests from loaded replicas to less solicited replicas. If such replicas do not exist, the replicas overlay self-adjusts to absorb the extra load without breaking the atomicity. We propose a distributed implementation of SAM where nodes exploit only a restricted local view of the system, for the sake of scalability. We provide a complete specification of our system and prove that it implements object atomicity. / Ce rapport présente une mémoire atomique auto-ajustable et auto-réparante en systèmes hautement dynamiques. Nous proposons une implémentation de celle-ci basée sur l'utilisation de techniques égales-à-égales (p2p). Cette solution appelée SAM, rassemble des thématiques de recherches aussi bien anciennes que récentes telles que les couches de communication p2p, les quorums dynamiques et la réplication contrôlée. Les noeuds de SAM forment un sur-graphe connecté. Une copie de chaque objet est répliquée à différents noeuds, appelés réplicas. Afin d'assurer l'atomicité de ces objets, nous utilisons des quorums, ensembles intersectés de réplicas. Ces quorums sont obtenus via une traversée déterministe effectuée au sein du graphe de communication. De plus ce graphe possède des propriétés auto-* : Celui-ci s'auto-répare à la volée lorsque des réplicas quittent le système et le nombre de réplicas s'auto-ajuste en fonction de la charge. Plus particulièrement, SAM réparti automatiquement la charge en distribuant les requêtes effectuées sur des noeuds surchargés à d'autres noeuds. Si tous les noeuds sont surchargés alors le sur-graphe s'auto-ajuste pour absorber la charge induite en garantissant l'atomicité. Dans ce rapport nous proposons une implementation distribuée de SAM où chaque noeud ne possède qu'une connaissance locale du système, permettant ainsi son utilisation à grande échelle. Nous spécifions formellement cet algorithme et prouvons qu'il satisfait la propriété d'atomicité des objets.
Document type :
Reports
Complete list of metadata

https://hal.inria.fr/inria-00000115
Contributor : Anne Jaigu <>
Submitted on : Friday, June 17, 2005 - 11:24:41 AM
Last modification on : Thursday, February 11, 2021 - 2:48:03 PM
Long-term archiving on: : Thursday, April 1, 2010 - 9:42:49 PM

Identifiers

  • HAL Id : inria-00000115, version 1

Citation

Emmanuelle Anceaume, Maria Gradinariu, Vincent Gramoli, Antonino Virgillito. SAM: Self* Atomic Memory for P2P Systems. [Research Report] PI 1717, 2005, pp.23. ⟨inria-00000115⟩

Share

Metrics

Record views

299

Files downloads

246