Polystyrene: the Decentralized Data Shape That Never Dies

Abstract : Decentralized topology construction protocols organize nodes along a predefined topology (e.g. a torus, ring, or hypercube). Such topologies have been used in many contexts ranging from routing and storage systems, to publish-subscribe and event dissemination. Since most topologies assume no correlation between the physical location of nodes and their positions in the topology, they do not handle catastrophic failures well, in which a whole region of the topology disappears. When this occurs, the overall shape of the system typically gets lost. This is highly problematic in applications in which overlay nodes are used to map a virtual data space, be it for routing, indexing or storage. In this paper, we propose a novel decentralized approach that maintains the initial shape of the topology even if a large (consecutive) portion of the topology fails. Our approach relies on the dynamic decoupling between physical nodes and virtual ones enabling a fast reshaping. For instance, our results show that a 51,200-node torus converges back to a full torus in only 10 rounds after 50% of the nodes have crashed. Our protocol is both simple and flexible and provides a novel form of collective survivability that goes beyond the current state of the art.
Type de document :
Communication dans un congrès
The 2014 IEEE 34th International Conference on Distributed Computing Systems (ICDCS 2014), Jun 2014, Madrid, Spain. pp.288 - 297, 2014, 〈http://www.ieee.org/〉. 〈10.1109/ICDCS.2014.37〉
Liste complète des métadonnées

Littérature citée [30 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01080608
Contributeur : François Taïani <>
Soumis le : mercredi 5 novembre 2014 - 16:32:33
Dernière modification le : lundi 3 décembre 2018 - 22:20:06
Document(s) archivé(s) le : vendredi 6 février 2015 - 10:45:12

Fichier

PolystyreneAlgo.pdf
Fichiers produits par l'(les) auteur(s)

Licence


Copyright (Tous droits réservés)

Identifiants

Citation

Simon Bouget, Anne-Marie Kermarrec, Hoel Kervadec, François Taïani. Polystyrene: the Decentralized Data Shape That Never Dies. The 2014 IEEE 34th International Conference on Distributed Computing Systems (ICDCS 2014), Jun 2014, Madrid, Spain. pp.288 - 297, 2014, 〈http://www.ieee.org/〉. 〈10.1109/ICDCS.2014.37〉. 〈hal-01080608〉

Partager

Métriques

Consultations de la notice

686

Téléchargements de fichiers

231