Well Balanced Designs for Data Placement

Jean-Claude Bermond 1 Alain Jean-Marie 2, 3 Dorian Mazauric 4, 5 Joseph Yu 6
1 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués, CRISAM - Inria Sophia Antipolis - Méditerranée
2 MAESTRO - Models for the performance analysis and the control of networks
CRISAM - Inria Sophia Antipolis - Méditerranée
4 ABS - Algorithms, Biology, Structure
CRISAM - Inria Sophia Antipolis - Méditerranée
5 GEOMETRICA - Geometric computing
CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Saclay - Ile de France
Abstract : The problem we consider in this article is motivated by data placement, in particular data replication in distributed storage and retrieval systems. We are given a set V of v servers along with b files (data, documents). Each file is replicated on exactly k servers. A placement consists in finding a family of b subsets of V (representing the files) called blocks, each of size k. Each server has some probability to fail and we want to find a placement which minimizes the variance of the number of available files. It was conjectured that there always exists an optimal placement (with variance better than that of any other placement for any value of the probability of failure). We show that the conjecture is true, if there exists a well balanced design, that is a family of blocks, each of size k, such that each j-element subset of V , 1 ≤ j ≤ k, belongs to the same or almost the same number of blocks (difference at most one). The existence of well balanced designs is a difficult problem as it contains as a subproblem the existence of Steiner systems. We completely solve the case k = 2 and give bounds and constructions for k = 3 and some values of v and b.
Type de document :
Article dans une revue
Journal of Combinatorial Designs, Wiley, 2016, 24 (2), pp.55-76. 〈10.1002/jcd.21506〉
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01223288
Contributeur : Alain Jean-Marie <>
Soumis le : lundi 2 novembre 2015 - 14:00:17
Dernière modification le : lundi 4 décembre 2017 - 15:14:19
Document(s) archivé(s) le : mercredi 3 février 2016 - 10:46:23

Fichiers

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

Identifiants

Citation

Jean-Claude Bermond, Alain Jean-Marie, Dorian Mazauric, Joseph Yu. Well Balanced Designs for Data Placement. Journal of Combinatorial Designs, Wiley, 2016, 24 (2), pp.55-76. 〈10.1002/jcd.21506〉. 〈hal-01223288〉

Partager

Métriques

Consultations de la notice

271

Téléchargements de fichiers

142