Extremal graphic model in optimizing fractional repetition codes for efficient storage repair
Guangping Xu, Qunfang Mao, Sheng Lin, Kai Shi, Hua Zhang · 2016
Consider that a set of balls of n different colors are thrown into m bins with the assumption that the ball number of each color is constant and the number of balls in each bin is also constant. Our optimal goal is to find a feasible placement such that the distinct colors of remaining balls should be at least c after removing any k bins (k ≤ m) with the minimum number of balls. We present that the optimal colored bins in bins is equivalent to the optimization of Fractional Repetition (FR) codes in distributed storage systems. Here balls correspond to coded packets and bins correspond to storage nodes. This problem can be represented as biregualr graph and then deduced to the Zarankiewicz problem, which is a well-known extremal graph theoretic problem. We present the problem with the relation to combinatorial design theory, especially t-designs and propose the explicit construction algorithm for the optimization problem from t-designs. Some constructions of the optimized FR codes by 2-designs are analyzed to tolerate the desired k fault-tolerance with c = n - 1.