Existence of Minimum-Repair-Bandwidth Cooperative Regenerating Codes
Kenneth W. Shum, Yuchong Hu · 2011
In distributed storage systems, a new class of fault-tolerant codes, called regenerating codes, was introduced in order to minimize the traffic required in repairing a failed storage node. Studies of regenerating codes in the literature mainly focus on repairing a single-node failure. Nevertheless, multiple-node failure is common in real systems. In this paper, we consider the problem of regenerating multiple failed nodes simultaneously and cooperatively. We give a lower bound of the repair- bandwidth under cooperative repair. The tightness of this lower bound is proved by constructing a flow in the information flow graph which matches this lower bound. Based on the construction of flow, we prove the existence of linear regenerating codes with repair-bandwidth equal to the lower bound, with an explicit bound on the required finite field size.