Premium
Well‐Balanced Designs for Data Placement
Author(s) -
Bermond JeanClaude,
JeanMarie Alain,
Mazauric Dorian,
Yu Joseph
Publication year - 2016
Publication title -
journal of combinatorial designs
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.618
H-Index - 34
eISSN - 1520-6610
pISSN - 1063-8539
DOI - 10.1002/jcd.21506
Subject(s) - conjecture , mathematics , variance (accounting) , set (abstract data type) , combinatorics , replication (statistics) , server , value (mathematics) , expected value , element (criminal law) , file size , discrete mathematics , existential quantification , computer science , statistics , accounting , world wide web , political science , law , business , programming language
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 that minimizes the variance of the number of available files. It was conjectured that there always exists an optimal placement (with variance better than 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 .