Abstract

We consider a generalization of the recently proposed gradient coding framework where a large dataset is divided across n workers and each worker transmits to a master node one or more linear combinations of the gradients over the data subsets assigned to it. Unlike the conventional framework which requires the master node to recover the sum of the gradients over all the data subsets in the presence of s straggler workers, we relax the goal of the master node to computing the sum of at least some α fraction of the gradients. The broad goal of our work is to study the optimal computation and communication load per worker for this approximate gradient coding framework. We begin by deriving a lower bound on the computation load of any feasible scheme and also propose a strategy which achieves this lower bound, albeit at the cost of high communication load and a number of data partitions which can be polynomial in the number of workers n. We then restrict attention to schemes which utilize a number of data partitions equal to n and propose schemes based on cyclic assignment which have a lower communication load. When each worker transmits a single linear combination, we also prove lower bounds on the computation load of any scheme using n data partitions.

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. We also give constructions of MRC with hierarchical locality for some parameters, whose field size is smaller than that of known constructions for general parameters. We also derive a field size lower bound on MRC with hierarchical locality.

Abstract

Blockchains have proven to provide a high level of performance in terms of security and reliability for various applications like cryptocurrencies and Internet-of-Things (IoT). Prism is a recent blockchain algorithm that achieves the physical limit on throughput and latency without compromising security. In recent days, reinforcement learning approaches are investi- gated in traditional blockchains, to improve performance. In this work, we apply Deep Reinforcement Learning (DRL) to one of the promising blockchain protocols, Prism, to optimize its performance. We propose a Deep Reinforcement Learning- based Prism Blockchain (DRLPB) scheme which dynamically optimizes the parameters of the Prism blockchain and helps in achieving a better performance. In DRLPB, we apply two widely used DRL algorithms, Dueling Deep Q Networks (DDQN) and Proximal Policy Optimization (PPO). This work presents a novel approach to applying DDQN and PPO to a blockchain protocol and comparing the performance. The DRLPB scheme adapts the Prism blockchain parameters to enhance the number of votes upto 84% more than Prism, while still preserving the security and latency performance guarantees of Prism.

Abstract

A code of length n is said to be (combinatorially) (ρ, L)-list decodable if the Hamming ball of radius ρn around any vector in the ambient space does not contain more than L codewords. We study a recently introduced class of higher order MDS codes, which are closely related (via duality) to codes that achieve a generalized Singleton bound for list decodability. For some ℓ ≥ 1, higher order MDS codes of length n, dimension k, and order ℓ are denoted as (n, k)-MDS(ℓ) codes. We present a number of results on the structure of these codes, identifying the ‘extend-ability’ of their parameters in various scenarios. Specifically, for some parameter regimes, we identify conditions under which (n1, k1)-MDS(ℓ1) codes can be obtained from (n2, k2)-MDS(ℓ2) codes, via various techniques. We believe that these results will aid in efficient constructions of higher order MDS codes. We also obtain a new field size upper bound for the existence of such codes, which arguably improves over the best known existing bound, in some parameter regimes. Due to space restrictions, the full version of this paper containing proofs of claims is made available in [1].

Abstract

We consider a distributed multi-user secret sharing setting consisting of a dealer, n storage nodes and m secrets where each user demands a t-subset of m secrets. The user downloads shares from the storage nodes based on the designed access structure and reconstructs its secrets. Earlier work in this setting dealt with the case of t = 1; in this work, we generalize it to natural numbers. We identify a necessary condition on the access structures to ensure weak secrecy. We also make a connection between the access structures for this problem and t-disjunct matrices. We apply various t-disjunct matrix constructions in this setting and compare their performance in terms of the number of storage nodes and communication complexity. We also derive bounds on the optimal communication complexity of a distributed secret sharing protocol. Finally, we characterize the capacity region of the DMUSS problem when the access structure is specified

Abstract

Reed-Solomon codes are polynomial evaluation codes and it has been shown that these can be efficiently repaired in the case of single node failures by considering the code symbols as vectors over a subfield and the helper nodes transfer multiple symbols over the subfield for repair. Tamo-Barg codes are a class of optimal LRCs which are also polynomial evaluation codes. These codes have Reed-Solomon codes as their local codes. In the case of single node failures, the repair takes place only within the local groups. In this paper, we address the question of whether the repair bandwidth within the local group can be further reduced by using the technique of Reed-Solomon repair. We give a construction based on cosets where the scheme requires lesser repair bandwidth than naive Reed-Solomon repair. We also give another construction based on optimal Reed-Solomon codes which achieve the cutset bound, where the Tamo-Barg codes are designed such that the local Reed-Solomon codes can be optimally repaired. We make the connection between these class of codes and the codes with local regeneration.

Abstract

In distributed storage systems, cooperative regener- ating 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 frame- work 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 explicit constructions of minimum bandwidth rack-aware cooperative regenerating codes and minimum storage rack-aware cooperative regenerating codes for a large range of parameters. We also consider another extension of minimum stor- age cooperative regenerating codes, in which we design slightly sub-optimal cooperative regenerating codes with much lower sub- packetization. -MSR codes are a class of codes introduced to tradeoff sub-packetization 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. Finally, we show the subpacketization level of -MSCR codes scales logarithmically in the number of nodes.

Abstract

Product codes are a class of codes which have generator matrices as the tensor product of the component codes and the codeword itself can be represented as an (m × n) array, where the component codes themselves are referred to as the row and column codes. Maximally recoverable product codes (MRPCs) are a class of codes which can recover from all information theoretically recoverable erasure patterns, given the a column and b row constraints imposed by the code. In this work, we derive puncturing and shortening properties of maximally recoverable product codes. We give a sufficient condition to characterize a certain subclass of erasure patterns as correctable and another necessary condition to characterize another subclass of erasure patterns as not correctable. In an earlier work, higher order MDS codes denoted by MDS(l) have been defined in terms of generic matrices and these codes have been shown to be constituent row codes for maximally recoverable product codes for the case of a = 1. We derive a certain inclusion-exclusion type principle for characterizing the dimension of intersection spaces of generic matrices. Applying this, we formally derive a relation between MDS(3) codes and points/lines of the associated projective space.

Abstract

Codes with locality allow for efficient recovery from single node failures by minimizing the number of nodes accessed to repair a failed node. These codes can also be extended to handle multiple erasures. Codes with hierarchical locality are another extension of codes with locality, which offer multiple levels of locality as the number of erasures increase. Maximally recoverable codes (MRC) are a class of codes, which satisfy the locality property and in addition also recover from all information theoretically recoverable erasure patterns. In this work, we construct MRC with hierarchical locality based on generator matrices of linearized Reed-Solomon codes and the field size is better than the earlier known construction. We also give a random construction of MRC with hierarchical locality and characterize the field size required. Finally, we present sparse generator matrices for MRC with locality and also sparse and balanced generator matrices for MRC with locality parameter 2 for large set of 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.Due to space restrictions, the full version of this paper, containing proofs and additional results, is made available in [1].