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

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

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

The problem of data exchange between multiple nodes with (not necessarily uniform) storage and communication capabilities models several current multi-user communication problems like Coded Caching, Data shuffling, Coded Computing, etc. The goal in such problems is to design communication schemes which accomplish the desired data exchange between the nodes with the optimal (minimum) amount of communication load. In this work, we present a converse to such a general data exchange problem between multiple nodes. The expression of the converse depends only on the number of bits to be moved between different subsets of nodes, and does not assume anything further specific about the parameters in the problem. Specific problem formulations, such as those in Coded Caching, Coded Data Shuffling, Coded Distributed Computing, and some of their variants, naturally can be seen as instances of this generic data exchange problem. Applying our generic converse to such problems, we recover known important converses for these settings and some of their variants in a simpler way. Further, for a generic coded caching problem with multiple transmitters, receivers and cache sizes, we show a new general converse which subsumes many existing results. We also employ our bound to obtain a new tight converse bound for the multi-node removal case in the Coded Data Rebalancing problem, in which nodes must exchange information to `rebalance' a storage cluster after some node failures occur. Finally we relate a `centralized' version of our bound to the known generalized independence number bound in index coding, and discuss our bound's tightness in this context.

Abstract

Coding theoretic techniques have been proposed for synchronous Gradient Descent (GD) on multiple servers to mitigate stragglers. These techniques provide the flexibility that the job is complete when any k out of n servers finish their assigned tasks. The task size on each server is found based on the values of k and n. However, it is assumed that all the n jobs are started when the job is requested. In contrast, we assume a tiered system, where we start with n1 ≥ k tasks, and on completion of c tasks, we start n2 – n1 more tasks. The aim is that as long as k servers can execute their tasks, the job gets completed. This paper exploits the flexibility that not all servers are started at the request time to obtain the achievable task sizes on each server. The task sizes are in general lower than starting all n2 tasks at the request times thus helping achieve lower task sizes which helps to reduce both the job completion time and the total server utilization.

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

Distributed databases often suffer unequal distribution of data among storage nodes, which is known asdata skew'. Data skew arises from a number of causes such as removal of existing storage nodes and addition of new empty nodes to the database. Data skew leads to performance degradations and necessitatesrebalancing'at regular intervals to reduce the amount of skew. We define an -balanced distributed database as a distributed database in which the storage across the nodes has uniform size, and each bit of the data is replicated in distinct storage nodes. We consider the problem of designing such balanced databases along with associated rebalancing schemes which maintain the -balanced property under node removal and addition operations. We present a class of -balanced databases (parameterized by the number of storage nodes) which have the property of structural invariance, ie, the databases designed for different number of storage nodes have the same structure. For this class of -balanced databases, we present rebalancing schemes which use coded transmissions between storage nodes, and characterize their communication loads under node addition and removal. We show that the communication cost incurred to rebalance our distributed database for node addition and removal is optimal, ie, it achieves the minimum possible cost among all possible balanced distributed databases and rebalancing schemes.

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

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

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