An extended least difference greedy (LDG) clique-cover algorithm for index coding

Abstract

In this thesis, we study the index coding problems for repair problems of distributed storage systems with local hierarchical structures. In distributed storage systems, it is well known that the maximum distance separable (MDS) erasure codes is the optimal scheme in terms of redundancy-reliability tradeoff. However, in real storage systems such as Hadoop distriubted file system which is used by Facebook and Yahoo, only 8 percent of the data is MDS encoded though it is still the most efficient. It is because of the serious transmission cost in the repair process of MDS coded distributed storage system, hence reducing the cost is the most important and challenging problem of researches on the distributed storage systems. We present that a repair problem of multiple failures in a distributed storage system with local hierarchy can be immediately reduced to an index coding problem. Consequently, numerous results in the field of index coding can be applied to the repair problems of distributed storage systems. Motivated by the fact, we proposed an efficient linear binary index coding algorithm named "The Extended LDG Algorithm". From the existing algorithm proposed by Birk and Kol (FOCS` 06), we develop 2 extensions which are "column merging" and "row addition and backward induction heuristic". Considering a transpose model of an index coding instance and cycles in the graph model of the index coding problem obtained by the existing algorithm, we improve performance of the algorithm and offer the lower number of transmitted blocks for a given index coding problem. In conclusion, we contribute to the repair problems of distributed storage systems with local hierarchical structures by developing an efficient index coding algorithm extended from the existing one.