Abstract

In distributed storage systems, cooperative regenerating codes tradeoff storage for repair bandwidth in the case of multiple node failures. In rack-aware distributed storage systems, there is no cost associated with transferring symbols within a rack. Hence, the repair bandwidth will only take into account cross-rack transfer. Rack-aware regenerating codes for the case of single node failures have been studied and their repair bandwidth tradeoff characterized. In this paper, we consider the framework of rack-aware cooperative regenerating codes for the case of multiple node failures where the node failures are uniformly distributed among a certain number of racks. We characterize the storage repair-bandwidth tradeoff as well as derive the minimum storage and minimum repair bandwidth points of the tradeoff. We also provide constructions of minimum bandwidth rack-aware cooperative regenerating codes for all parameters.

Abstract

Locally recoverable codes (LRCs) are known to reduce the repair locality, i.e., the number of nodes accessed during node repair, in distributed storage systems. Regenerating codes, on the other hand, offer a decreased repair bandwidth, which is the repair traffic incurred during node repairs. Locally regenerating codes (LRGCs), which are constructed via intertwining regenerating codes of smaller block lengths, simultaneously offer a small repair locality and repair bandwidth. In this letter, we construct a family of LRGCs where the constituent codes are bandwidth-efficient, minimum bandwidth cooperative regenerating codes. The newly constructed LRGCs are optimal with respect to both minimum distance and rate.

Abstract

—Blockchain is a distributed ledger with wide applications. Due to the increasing storage requirement for blockchains, the computation can be afforded by only a few miners. Sharding has been proposed to scale blockchains so that storage and transaction efficiency of the blockchain improves at the cost of security guarantee. This paper aims to consider a new protocol, Secure-Repair-Blockchain (SRB), which aims to decrease the storage cost at the miners. In addition, SRB also decreases the bootstrapping cost, which allows for new miners to easily join a sharded blockchain. In order to reduce storage, coding-theoretic techniques are used in SRB. In order to decrease the amount of data that is transferred to the new node joining a shard, the concept of exact repair secure regenerating codes is used. The proposed blockchain protocol achieves lower storage than those that do not use coding, and achieves lower bootstrapping cost as compared to the different baselines

Abstract

An index code for broadcast channel with receiver side information is locally decodable if each receiver can decode its demand by observing only a subset of the transmitted codeword symbols instead of the entire codeword. Local decodability in index coding is known to reduce receiver complexity, improve user privacy and decrease decoding error probability in wireless fading channels. Conventional index coding solutions assume that the receivers observe the entire codeword, and as a result, for these codes the number of codeword symbols queried by a user per decoded message symbol, which we refer to as locality, could be large. In this paper, we pose the index coding problem as that of minimizing the broadcast rate for a given value of locality (or vice versa) and designing codes that achieve the optimal trade-off between locality and rate. We identify the optimal broadcast rate corresponding to the minimum possible value of locality for all single unicast problems. We present new structural properties of index codes which allow us to characterize the optimal trade-off achieved by: vector linear codes when the side information graph is a directed cycle; and scalar linear codes when the minrank of the side information graph is one less than the order of the problem. We also identify the optimal trade-off among all codes, including non-linear codes, when the side information graph is a directed 3-cycle. Finally, we present techniques to design locally decodable index codes for arbitrary single unicast problems and arbitrary values of locality. Index Terms— Broadcast rate, directed cycle, index coding, linear codes, locally decodable codes, minrank.

Abstract

An index code is said to be locally decodable if each receiver can decode its demand using its side information and by querying only a subset of the transmitted codeword symbols instead of observing the entire codeword. Local decodability can be a beneficial feature in some communication scenarios, such as when the receivers can afford to listen to only a part of the transmissions because of limited availability of power. The locality of an index code is the ratio of the maximum number of codeword symbols queried by a receiver to the message length. In this paper we analyze the optimum locality of linear codes for the family of index coding problems whose min-rank is one less than the number of receivers in the network. We first derive the optimal trade-off between the index coding rate and locality with vector linear coding when the side information graph is a directed cycle. We then provide the optimal trade-off …

Abstract

Cooperative regenerating codes are regenerating codes designed to tradeoff storage for repair bandwidth in case of multiple node failures. Minimum storage cooperative regenerating (MSCR) codes are a class of cooperative regenerating codes which achieve the minimum storage point of the tradeoff. Recently, these codes have been constructed for all possible parameters (n, k, d, h), where h erasures are repaired by contacting any d surviving nodes. However, these constructions have very large sub-packetization. ε-MSR codes are a class of codes introduced to tradeoff subpacketization level for a slight increase in the repair bandwidth for the case of single node failures. We introduce the framework of ε-MSCR codes which allow for a similar tradeoff for the case of multiple node failures. We present a construction of ε-MSCR codes, which can recover from two node failures, by concatenating a class of MSCR codes and scalar linear codes. We give a repair procedure to repair the ε-MSCR codes in the event of two node failures and calculate the repair bandwidth for the same. We characterize the increase in repair bandwidth incurred by the method in comparison with the optimal repair bandwidth given by the cut-set bound. Finally, we show the subpacketization level of ε-MSCR codes scales logarithmically in the number of nodes

Abstract

Maximally recoverable codes are a class of codes which recover from all potentially recoverable erasure patterns given the locality constraints of the code. In earlier works, these codes have been studied in the context of codes with locality. The notion of locality has been extended to hierarchical locality, which allows for locality to gradually increase in levels with the increase in the number of erasures. We consider the locality constraints imposed by codes with two-level hierarchical locality and define maximally recoverable codes with data-local and local hierarchical locality. We derive certain properties related to their punctured codes and minimum distance. We give a procedure to construct hierarchical data-local MRCs from hierarchical local MRCs. We provide a construction of hierarchical local MRCs for all parameters. For the case of one global parity, we provide a different construction of hierarchical local MRC over a lower field size

Abstract

Polar codes, introduced by Arikan, achieve the capacity of arbitrary binary-input discrete memoryless channel W under successive cancellation decoding. Any such channel having capacity I(W) and for any coding scheme allowing transmission at rate R, scaling exponent is a parameter which characterizes how fast gap to capacity decreases as a function of code length N for a fixed probability of error. The relation between them is given by N⩾α/(I(W)−R)μ. Scaling exponent for kernels of small size up to L=8 have been exhaustively found. In this paper, we consider product kernels TL obtained by taking Kronecker product of component kernels. We derive the properties of polarizing product kernels relating to number of product kernels, self duality and partial distances in terms of the respective properties of the smaller component kernels. Subsequently, polarization behavior of component kernel Tl is used to calculate scaling exponent of TL=T2⊗Tl. Using this method, we show that μ(T2⊗T5)=3.942. Further, we employ a heuristic approach to construct good kernel of L=14 from kernel having size l=8 having best μ and find μ(T2⊗T7)=3.485.

Abstract

Index coding for broadcast channels allows each receiver or client to retrieve its demanded message from its side information and the transmitted codeword. In general, a client may have to observe the entire codeword to decode its demanded message. However, downloading or querying the codeword symbols might involve costs at a client - such as network utilization costs and storage. Traditional index coding does not consider this client perspective, and as a result, for these codes the number of codeword symbols queried by a client per decoded message symbol, which we refer to as locality, could be large. In this paper we study a `client aware' approach to index coding by viewing the problem as a trade-off between the achievable broadcast rate and locality, where the objective is to minimize the rate for a given value of locality and vice versa. We first consider the minimum possible locality 1 and show that the …

Abstract

Given a topology of local parity-check constraints, a maximally recoverable code (MRC) can correct all erasure patterns that are information-theoretically correctable. In a grid-like topology, there are a local constraints in every column forming a column code, b local constraints in every row forming a row code, and h global constraints in an (m × n) grid of codeword. Recently, Gopalan et al. initiated the study of MRCs under grid-like topology, and derived a necessary and sufficient condition, termed as the regularity condition, for an erasure pattern to be recoverable when a = 1, h = 0. In this paper, we consider MRCs for product topology ( h = 0). First, we construct a certain bipartite graph based on the erasure pattern satisfying the regularity condition for product topology (any a, b, h = 0) and show that there exists a complete matching in this graph. We then present an alternate direct proof of the sufficient condition when a = 1, h = 0. We later extend our technique to study the topology for a = 2, h = 0, and characterize a subset of recoverable erasure patterns in that case. For both a = 1, 2, our method of proof is uniform, i.e., by constructing tensor product G col ⊗ G row of generator matrices of column and row codes such that certain square sub-matrices retain full rank. The full-rank condition is proved by resorting to the matching identified earlier and also another set of matchings in erasure sub-patterns.