Well Balanced Designs for Data Placement

Jean-Claude Bermond 1 Alain Jean-Marie 2, 3 Dorian Mazauric 1, 3 Joseph Yu 1
1 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
2 MAORE - Méthodes Algorithmes pour l'Ordonnancement et les Réseaux
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
3 MAESTRO - Models for the performance analysis and the control of networks
CRISAM - Inria Sophia Antipolis - Méditerranée
Résumé : Nous considérons un problème motivé par le placement de données, en particulier la réplication de données dans les systèmes distribués de stockage et de récupération. Étant donné un ensemble V de v serveurs et un ensemble de b fichiers (données, documents), chaque fichier est répliqué dans exactement k serveurs. Un placement est une famille de b sous-ensembles de V (représentant les fichiers) appel ́es blocks, chacun étant de taille k. Chaque serveur a une certaine probabilité de tomber en panne et nous cherchons un placement qui minimise la variance du nombre de fichiers disponibles. Il a été conjecturé qu’il existe toujours un placement qui est optimal quelle que soit la probabilité de panne. Nous prouvons que la conjecture est vraie s’il existe une configuration équilibrée, c’est-a`-dire une famille de blocks, chacun de taille k, telle que chaque sous-ensemble de V de taille j, 1 ≤ j ≤ k, appartient au même nombre ou au quasi même nombre de blocks (différence d’au plus un). L’existence de configurations équilibrées est un problème difficile car il inclut comme sous-problème l’existence de systèmes de Steiner. Nous résolvons complètement le cas k = 2 et nous prouvons des bornes et des constructions pour k = 3 et certaines valeurs de v et de b.
Type de document :
Rapport
[Research Report] RR-7725, Inria. 2011


https://hal.inria.fr/inria-00618656
Contributeur : Dorian Mazauric <>
Soumis le : vendredi 14 novembre 2014 - 14:02:16
Dernière modification le : vendredi 16 septembre 2016 - 15:07:13
Document(s) archivé(s) le : lundi 16 février 2015 - 15:50:17

Fichier

RR-7725.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00618656, version 3

Collections

Citation

Jean-Claude Bermond, Alain Jean-Marie, Dorian Mazauric, Joseph Yu. Well Balanced Designs for Data Placement. [Research Report] RR-7725, Inria. 2011. <inria-00618656v3>

Exporter

Partager

Métriques

Consultations de
la notice

150

Téléchargements du document

109