Explicit Construction of Optimal Exact Regenerating Codes for Distributed Storage

Erasure coding techniques are used to increase the reliability of distributed storage systems while minimizing storage overhead. Also of interest is minimization of the bandwidth required to repair the system following a node failure. In a recent paper, Wu et al. characterize the tradeoff between the repair bandwidth and the amount of data stored per node. They also prove the existence of regenerating codes that achieve this tradeoff. In this paper, we introduce Exact Regenerating Codes, which are regenerating codes possessing the additional property of being able to duplicate the data stored at a failed node. Such codes require low processing and communication overheads, making the system practical and easy to maintain. Explicit construction of exact regenerating codes is provided for the minimum bandwidth point on the storage-repair bandwidth tradeoff, relevant to distributed-mail-server applications. A sub-space based approach is provided and shown to yield necessary and sufficient conditions on a linear code to possess the exact regeneration property as well as prove the uniqueness of our construction. Also included in the paper, is an explicit construction of regenerating codes for the minimum storage point for parameters relevant to storage in peer-to-peer systems. This construction supports a variable number of nodes and can handle multiple, simultaneous node failures. All constructions given in the paper are of low complexity, requiring low field size in particular.

Fast edge splitting and Edmonds' arborescence construction for unweighted graphs

Given an unweighted undirected or directed graph with n vertices, m edges and edge connectivity c, we present a new deterministic algorithm for edge splitting. Our algorithm splits-off any specified subset S of vertices satisfying standard conditions (even degree for the undirected case and in-degree ≥ out-degree for the directed case) while maintaining connectivity c for vertices outside S in Õ(m+nc2) time for an undirected graph and Õ(mc) time for a directed graph. This improves the current best deterministic time bounds due to Gabow [8], who splits-off a single vertex in Õ(nc2+m) time for an undirected graph and Õ(mc) time for a directed graph. Further, for appropriate ranges of n, c, |S| it improves the current best randomized bounds due to Benczúr and Karger [2], who split-off a single vertex in an undirected graph in Õ(n2) Monte Carlo time. We give two applications of our edge splitting algorithms. Our first application is a sub-quadratic (in n) algorithm to construct Edmonds' arborescences. A classical result of Edmonds [5] shows that an unweighted directed graph with c edge-disjoint paths from any particular vertex r to every other vertex has exactly c edge-disjoint arborescences rooted at r. For a c edge connected unweighted undirected graph, the same theorem holds on the digraph obtained by replacing each undirected edge by two directed edges, one in each direction. The current fastest construction of these arborescences by Gabow [7] takes Õ(n2c2) time. Our algorithm takes Õ(nc3+m) time for the undirected case and Õ(nc4+mc) time for the directed case. The second application of our splitting algorithm is a new Steiner edge connectivity algorithm for undirected graphs which matches the best known bound of Õ(nc2 + m) time due to Bhalgat et al [3]. Finally, our algorithm can also be viewed as an alternative proof for existential edge splitting theorems due to Lovász [9] and Mader [11].

A general construction of space-time trellis codes for PSK signal sets

The diversity order and coding gain are crucial for the performance of a multiple antenna communication system. It is known that space-time trellis codes (STTC) can be used to achieve these objectives. In particular, we can use STTCs to obtain large coding gains. Many attempts have been made to construct STTCs which achieve full-diversity and good coding gains, though a general method of construction does not exist. Delay diversity code (rate-1) is known to achieve full-diversity, for any number of transmit antennas and any signal set, but does not give a good coding gain. A product distance code based delay diversity scheme (Tarokh, V. et al., IEEE Trans. Inform. Theory, vol.44, p.744-65, 1998) enables one to improve the coding gain and construct STTCs for any given number of states using coding in conjunction with delay diversity; it was stated as an open problem. We achieve such a construction. We assume a shift register based model to construct an STTC for any state complexity. We derive a sufficient condition for this STTC to achieve full-diversity, based on the delay diversity scheme. This condition provides a framework to do coding in conjunction with delay diversity for any signal constellation. Using this condition, we provide a formal rate-1 STTC construction scheme for PSK signal sets, for any number of transmit antennas and any given number of states, which achieves full-diversity and gives a good coding gain.

Construction of Block Orthogonal STBCs and Reducing Their Sphere Decoding Complexity

Construction of high rate Space Time Block Codes (STBCs) with low decoding complexity has been studied widely using techniques such as sphere decoding and non Maximum-Likelihood (ML) decoders such as the QR decomposition decoder with M paths (QRDM decoder). Recently Ren et al., presented a new class of STBCs known as the block orthogonal STBCs (BOSTBCs), which could be exploited by the QRDM decoders to achieve significant decoding complexity reduction without performance loss. The block orthogonal property of the codes constructed was however only shown via simulations. In this paper, we give analytical proofs for the block orthogonal structure of various existing codes in literature including the codes constructed in the paper by Ren et al. We show that codes formed as the sum of Clifford Unitary Weight Designs (CUWDs) or Coordinate Interleaved Orthogonal Designs (CIODs) exhibit block orthogonal structure. We also provide new construction of block orthogonal codes from Cyclic Division Algebras (CDAs) and Crossed-Product Algebras (CPAs). In addition, we show how the block orthogonal property of the STBCs can be exploited to reduce the decoding complexity of a sphere decoder using a depth first search approach. Simulation results of the decoding complexity show a 30% reduction in the number of floating point operations (FLOPS) of BOSTBCs as compared to STBCs without the block orthogonal structure.

OPTIMALITY OF THE PRODUCT-MATRIX CONSTRUCTION FOR SECURE MSR REGENERATING CODES

In this paper, we consider the security of exact-repair regenerating codes operating at the minimum-storage-regenerating (MSR) point. The security requirement (introduced in Shah et. al.) is that no information about the stored data file must be leaked in the presence of an eavesdropper who has access to the contents of l(1) nodes as well as all the repair traffic entering a second disjoint set of l(2) nodes. We derive an upper bound on the size of a data file that can be securely stored that holds whenever l(2) <= d - k +1. This upper bound proves the optimality of the product-matrix-based construction of secure MSR regenerating codes by Shah et. al.