Comparing Various Locality Approaches for Codes Repairing Two Erasures

Abstract

For many IT applications information is stored digitally across multiple storage units and needs to be available continuously. Due to malfunctions data servers might be erased or temporarily inaccessible. Different approaches using linear coding theory have been proposed in order to retrieve the content of erased servers from repair sets containing a selection of the remaining servers. This thesis focuses on comparing various repair methods for two erasures; disjoint parallel repair which protects each erasure by multiple disjoint repair sets, cooperative repair which uses a single repair set to repair all erasures at once and sequential repair which repairs erasures individually by using already repaired erasures. Coding inevitably induces storage overhead measured by the information rate. The applied method creates transmission overhead measured by locality, which concerns the number of servers accessed to perform erasure repair. The comparison mainly consists of appropriately computing minimal transmission overhead for these methods given a predetermined storage overhead. It is shown that Hamming codes have the best possible transmission overhead applying the cooperative method. The next best method is sequential repair, whereas disjoint parallel repair is too restrictive for two erasure repair with Hamming codes. For a generalized parity code it is demonstrated that the sequential method can repair more erasures than the disjoint parallel approach, and reach a better locality than the cooperative method. In general, the cooperative method eciently uses access to servers in order to reduce transmission overhead. For the same purpose, the sequential method uses already repaired servers allowing smaller repair sets to be accessed. In any repair process it is key to nd optimal combinations of a method and code which exploit these qualities. The cooperative method applied to Hamming codes and the sequential method combined with generalized parity codes prove to be high-ranking combinations in this regard.