Codes with locality without any global paritycheck constraints apart from those generated by local codes' constraints have recently found a unique application in decentralized systems. In response to this, we proposed in previous work, a new class of block circulant (BC) codes possessing certain structure in the arrangement of parity-check constraints referred to as a block circulant topology. The BC topology$T_{[\mu, \lambda, \omega]}(\rho)$and$\mathbf{B C}$codes$C_{\mathbf{B C}}[\mu, \lambda, \omega, \rho]$are parameterized by integers$\lambda \geq 2, \omega \geq 2, \rho \geq 2$and$\mu$a multiple of$\lambda$. In this work, we show that the rate and the minimum distance of the BC code scale with corresponding metrics of its local codes in a manner that can not be realized by well-known linear array and product topologies, thus widening the possible regime of operation. We also provide an efficient erasure-correcting decoder for$C_{\mathbf{B C}}[\mu, \lambda=3, \omega, \rho]$, while such a decoder was earlier known only for$\lambda=2$. The decoding algorithm uses a novel mechanism that iteratively corrects erasures from either a single or a triplet of local codes. We show that the minimum distance of$C_{\mathbf{B C}}[\mu, \lambda=3, \omega, \rho]$is$3 \rho+1$, whereas the same result was earlier available under a constraint that$\mu=2^{a} \cdot 3$for some integer$a$.

In this paper, we design a family of [n, k, d] block circulant codes that consist of many [n0≪n, k0≪k, d0d] local codes and that satisfy two properties: (1) the code supports distributed decoding of up to (d− 1) erasures relying only on local codes without a central coordinator, and (2) it is amenable to low complexity verification of code symbols using a cryptographic commitment scheme. These properties make the code ideal for use in protocols that address the data availability problem in blockchain networks. Moreover, the code outperforms the currently used 2D Reed-Solomon (RS) code with a larger relative minimum distance (d/n), as desired in the protocol, for a given rate (k/n) in the high-rate regime. The code is designed in two steps. First, we develop the topology, i.e., the structure of linear dependence relations among code symbols, and define it as the block circulant topologyT[μ,λ,ω](ρ). In this topology, there are μ local codes, each constrained by ρ parity checks. The set of symbols of a local code intersects with another in a uniform pattern, determined by two parameters, namely theoverlap factorλ and theoverlap widthω. Next, we instantiate the topology, i.e., specify the coefficients of the linear dependence relations, to construct the block circulant codesCBC[μ, λ, ω, ρ]. Every local code is a [λω+ρ, λω, ρ+1] generalized RS code. The block circulant code hasn= μ(ρ + ω), k = μω and we show that, under certain conditions,d= λρ + 1. For λ = 2, we prove that d = 2ρ+1 always, and provide an efficient, parallelizable erasure-correcting decoder that fully recovers the codeword when there are ≤ 2ρ erasures. The decoder uses a novel decoding mechanism that iteratively recovers erasures from either local codes or pairs of them.

A family of$(n=2^{\ell}.M=2^{k_{\ell}}\ . \ d=2)$, binary constant-weight codes for any positive integer$\ell > 3, k_{\ell}= \displaystyle \frac{\ell(\ell+1)}{9}-1$was recently proposed in literature [1]. As infor-mation is encoded in the gaps (cyclically counted) between successive 1 's, we refer to these codes as cyclic-gap constant weight codes denoted by$C_{G}[\ell$. These codes admit very low-complexity algorithms for mapping and demapping between message and codeword vectors, fully eliminating the need for costly computations of binomial coefficients. In this paper, we study maximum-likelihood (ML) decoding of these codes under additive white Gaussian noise channels. Since the minimum distance of the code$d=2$, hard-decision decoders can not correct errors. Motivated by the error-correcting capability of soft-decision Wagner-rule decoder for single-parity-check codes, we derive an ML decoder for$C_{G}[\ell$. We also derive a low-complexity approximation of the ML decoder with a time-complexity of$O(n\log n^{\backslash },$. The algorithm is based on a novel technique of traversal through the Hasse diagram of a partially ordered set of all ℓ-subsets of$\{1, 2, \ldots, n\}$in a breadth-first manner. Our approach is applicable to decoding of any binary constant-weight code and therefore is of general interest. We simulate the performance of the low-complexity decoder for the$(8, 32, 2)$code$C_{G}$[3] and show that it performs almost similar to ML when a parameter$\lambda_{\mathrm{m}\mathrm{m}}$(that determines how far to traverse in the Hasse diagram) is taken to be 3. We also show by simulation that it performs better than a comparable$[8, 5, 2]$linear code under ML decoding.

Abstract In this paper, we focus on the design of binary constant weight codes that admit low-complexity encoding and decoding algorithms, and that have size $$M=2^k$$ M = 2 k so that codewords can conveniently be labeled with binary vectors of length k. For every integer $$\ell \ge 3$$ ℓ ≥ 3 , we construct a $$(n=2^\ell , M=2^{k_{\ell }}, d=2)$$ ( n = 2 ℓ , M = 2 k ℓ , d = 2 ) constant weight code $${{{\mathcal {C}}}}[\ell ]$$ C [ ℓ ] of weight $$\ell $$ ℓ by encoding information in the gaps between successive 1’s of a vector, and call them as cyclic-gap constant weight codes. The code is associated with a finite integer sequence of length $$\ell $$ ℓ satisfying a constraint defined as anchor-decodability that is pivotal to ensure low complexity for encoding and decoding. The time complexity of the encoding algorithm is linear in the input size k, and that of the decoding algorithm is poly-logarithmic in the input size n, discounting the linear time spent on parsing the input. Both the algorithms do not require expensive computation of binomial coefficients, unlike the case in many existing schemes. Among codes generated by all anchor-decodable sequences, we show that $${{{\mathcal {C}}}}[\ell ]$$ C [ ℓ ] has the maximum size with $$k_{\ell } \ge \ell ^2-\ell \log _2\ell + \log _2\ell - 0.279\ell - 0.721$$ k ℓ ≥ ℓ 2 - ℓ log 2 ℓ + log 2 ℓ - 0.279 ℓ - 0.721 . As k is upper bounded by $$\ell ^2-\ell \log _2\ell +O(\ell )$$ ℓ 2 - ℓ log 2 ℓ + O ( ℓ ) information-theoretically, the code $${{{\mathcal {C}}}}[\ell ]$$ C [ ℓ ] is optimal in its size with respect to two higher order terms of $$\ell $$ ℓ . In particular, $$k_\ell $$ k ℓ meets the upper bound for $$\ell =3$$ ℓ = 3 and one-bit away for $$\ell =4$$ ℓ = 4 . On the other hand, we show that $${{{\mathcal {C}}}}[\ell ]$$ C [ ℓ ] is not unique in attaining $$k_{\ell }$$ k ℓ by constructing an alternate code $$\mathcal{{\hat{C}}}[\ell ]$$

The growing privacy concerns and the communication costs associated with transmitting raw data have resulted in techniques like federated learning, where the machine learning models are trained at the edge nodes, and the parameter updates are shared with a central server. Because communications from the edge nodes are often unreliable, a hierarchical setup involving intermediate helper nodes is considered. The communication links between the edges and the helper nodes are error-prone and are modeled as straggling/failing links. To overcome the issue of link failures, coding techniques are proposed. The edge nodes communicate encoded versions of the model updates to the helper nodes, which pass them on to the master after suitable aggregation. The primary work in this area uses repetition codes and Maximum Distance Separable (MDS) codes at the edge nodes to arrive at the Aligned Repetition Coding (ARC) and Aligned MDS Coding (AMC) schemes, respectively. We propose using vector codes, specifically a family of layered MDS codes parameterized by a variable ν, at the edge nodes. For the proposed family of codes, suitable aggregation strategies at the helper nodes are also developed. At the extreme values of ν, our scheme matches the communication costs incurred by the ARC and AMC schemes, resulting in a graceful transition between these schemes.

A transaction record in a sharded blockchain can be represented as a two-dimensional array of integers with row-index associated to an account, column-index to a shard and the entry to the transaction amount. In a blockchain-based cryptocurrency system with coded sharding, a transaction record of a given epoch of time is encoded using a maximum-distance-separable code considering the entries as finite-field symbols. Each column of the resultant coded array is then stored in a server. In this paper, we propose a privacy-preserving multi-round protocol that allows a remote client to retrieve from a coded blockchain system the sum of transaction amounts belonging to two different epochs of time, but to the same ac-count. At the core of the protocol lies an algorithm for a remote client to privately compute a non-linear function referred to as integer addition of two finite-field symbols representing integer numbers, in the presence of curious-but-honest adversaries. Applying it to balance-checking in a cryptocurrency system, the protocol guarantees information-theoretic privacy on account number and shard number thereby ensuring perfect user anonymity, and also maintains confidentiality of half of the input bits on average. The protocol turns out to be a useful primitive for balance-checking in lightweight clients of a PolyShard-ed blockchain.

Increasing amount of data generated at edge nodes and quest for privacy have resulted in learning at the edge. Computations are performed at edge devices and outputs are communicated to a central node for updating the model. The edge nodes are available intermittently and are connected via low-bandwidth links. The edge nodes communicate local gradients to helper nodes, and these helpers forward messages to the central node after possible aggregation. Recently, schemes using repetition codes and maximum-distance-separable (MDS) codes, respectively known as aligned repetition coding (ARC) and aligned MDS coding (AMC) schemes, were proposed. It was observed that the communication cost at edge nodes becomes optimal in the AMC scheme, at the expense of an increased cost of communication incurred by helpers. An upper bound on the communication cost at helpers for the AMC scheme was known in literature. In this paper, a tradeoff between communication costs at edge nodes and at helper nodes is established with the help of newly proposed pyramid scheme. The scheme makes use of well-known class of pyramid codes, thus expanding the realm of application of locally repairable codes to distributed learning. The communication costs both at helper nodes and at edge nodes are exactly characterized. Using the developed technique, the exact communication cost at helper nodes can be computed for the AMC scheme as well. Next, we come up with a technique to improve the aggregation strategy of both pyramid and AMC schemes, that yields significant reduction in communication cost at helpers without changing parameters of the code used by edges. Finally, we present a greedy algorithm to improve the aggregation strategy of the ARC scheme, achieving significantly reduced communication cost at helpers.

The increasing amount of data generated at the edge/client nodes and the privacy concerns have resulted in learning at the edge, in which the computations are performed at edge devices and are communicated to a central node for updating the model. The edge nodes have low bandwidth and may be available only intermittently. There are helper nodes present in the network that aid the edge nodes in the communication to the server. The edge nodes communicate the local gradient to helper nodes which relay these messages to the central node after possible aggregation. Recently, schemes using repetition codes and maximum-distance-separable (MDS) codes were proposed. It was observed that in MDS scheme the communication between edge nodes and helper nodes is optimal but with an increased cost of communication between helper and master. An upper bound on the communication cost between helpers and master was obtained. In this paper, a tradeoff between communication costs at edge nodes and helper nodes is established with the help of pyramid codes, a well-known class of locally repairable codes. The communication costs at both the helper nodes and edge nodes are exactly characterized. Using the developed technique, the exact communication cost at helper nodes can be computed for the scheme using MDS codes.

In present blockchain systems, privacy of transactions is maintained by keeping the identity of accounts anonymous. The associated pseudonyms are ephemeral in nature, and can not be easily traced back to the real identity. An alternate infallible approach is to make use of private information retrieval (PIR) protocols that enable users to fetch details of transactions without revealing which transactions they seek. In this paper, we formalize this approach for blockchain systems that employ coded sharding. We present a PIR protocol for private data access, in particular private balance-checking, in blockchain systems when data is stored using generalized Reed-Solomon codes. Our protocol can be readily applied to the PolyShard scheme that has been recently proposed as a method to build truly scalable blockchain system.

This paper presents an explicit construction for an ((n = 2qt, k = 2q{t-1), d = n - (q + 1)), (α = q(2q)t-1,β = α/q)) regenerating code over a field Fqoperating at the Minimum Storage Regeneration (MSR) point. The MSR code can be constructed to have rate k/n as close to 1 as desired, sub-packetization level α ≤ rn/rfor r = (n - k), field size Q no larger than n and where all code symbols can be repaired with the same minimum data download. This is the first-known construction of such an MSR code for d <; (n - 1).

In this paper, we study the notion of codes with hierarchical locality that is identified as another approach to local recovery from multiple erasures. The well-known class of codes with locality is said to possess hierarchical locality with a single level. In a code with two-level hierarchical locality, every symbol is protected by an inner-most local code, and another middle-level code of larger dimension containing the local code. We first consider codes with two levels of hierarchical locality, derive an upper bound on the minimum distance, and provide optimal code constructions of low field-size under certain parameter sets. Subsequently, we generalize both the bound and the constructions to hierarchical locality of arbitrary levels.

We present a high-rate (n, k, d = n − 1)-MSR code with a sub-packetization level that is polynomial in the dimension k of the code. While polynomial sub-packetization level was achieved earlier for vector MDS codes that repair systematic nodes optimally, no such MSR code construction is known. In the low-rate regime (i. e., rates less than one-half), MSR code constructions with a linear sub-packetization level are available. But in the high-rate regime (i. e., rates greater than one-half), the known MSR code constructions required a sub-packetization level that is exponential in k. In the present paper, we construct an MSR code for d = n − 1 with a fixed rate equation, achieveing a sub-packetization level α = O(kt). The code allows help-by-transfer repair, i. e., no computations are needed at the helper nodes during repair of a failed node.

The characterization of the storage-repair bandwidth tradeoff of (n, k, d)-regenerating codes under the exact-repair setting remains an open problem. The problem has been solved only for the special case of (n, k, d) = (4, 3, 3). In the present paper, we characterize the tradeoff for the larger family of parameters (n, k = 3, d = n - 1). This is accomplished by constructing an (n, k <; d, d)-regenerating code, referred to as the improved layered code. In the case when (n, k = 3, d = n - 1), the code operates on a point that coincides with an interior point of a recently derived outer bound on the tradeoff. The code also achieves an interior point on the outer bound for the parameter set (n, k = 4, d = n - 1).

A new class of exact-repair regenerating codes is constructed by stitching together shorter erasure correction codes, where the stitching pattern can be viewed as block designs. The proposed codes have the help-by-transfer property where the helper nodes simply transfer part of the stored data directly, without performing any computation. This embedded error correction structure makes the decoding process straightforward, and in some cases the complexity is very low. We show that this construction is able to achieve performance better than space-sharing between the minimum storage regenerating codes and the minimum repair-bandwidth regenerating codes, and it is the first class of codes to achieve this performance. In fact, it is shown that the proposed construction can achieve a nontrivial point on the optimal functional-repair tradeoff, and it is asymptotically optimal at high rate, i.e., it asymptotically approaches the minimum storage and the minimum repair-bandwidth simultaneously.

While the tradeoff between the amount of data stored and the repair bandwidth of an (n, k, d) regenerating code has been characterized under functional repair (FR), the case of exact repair (ER) remains unresolved. It is known that there do not exist ER codes which lie on the FR tradeoff at most of the points. The question as to whether one can asymptotically approach the FR tradeoff was settled recently by Tian who showed that in the (4, 3, 3) case, the ER region is bounded away from the FR region. The FR tradeoff serves as a trivial outer bound on the ER tradeoff. In this paper, we extend Tian's results by establishing an improved outer bound on the ER tradeoff which shows that the ER region is bounded away from the FR region, for any (n, k, d). Our approach is analytical and builds upon the framework introduced earlier by Shah et. al. Interestingly, a recently-constructed, layered regenerating code is shown to achieve a point on this outer bound for the (5, 4, 4) case. This represents the first-known instance of an optimal ER code that does not correspond to a point on the FR tradeoff.

In this paper, we provide explicit constructions for a class of exact-repair regenerating codes that possess a layered structure. These regenerating codes correspond to interior points on the storage-repair-bandwidth tradeoff where the cut-set bound of network coding is known to be not achievable under exact repair. The codes presented in this paper compare very well in comparison to schemes that employ space-sharing between MSR and MBR points, and come closest of all-known explicit constructions to interior points of the tradeoff. The codes can be constructed for a wide range of parameters, are high-rate, can repair multiple nodes simultaneously and no computation at helper nodes is required to repair a failed node. We also construct optimal codes with locality in which the local codes are layered regenerating codes.

In this paper, we study the diversity-multiplexing-gain tradeoff (DMT) of wireless relay networks under the half-duplex constraint. It is often unclear what penalty if any, is imposed by the half-duplex constraint on the DMT of such networks. We study two classes of networks; the first class, called KPP(I) networks, is the class of networks with the relays organized inKparallel paths between the source and the destination. While we assume that there is no direct source-destination path, theKrelaying paths can interfere with each other. The second class, termed as layered networks, is comprised of relays organized in layers, where links exist only between adjacent layers. We present a communication scheme based on static schedules and amplify-and-forward relaying for these networks. We also show that for KPP(I) networks with K≥3, the proposed schemes can achieve full-duplex DMT performance, thus demonstrating that there is no performance hit on the DMT due to the half-duplex constraint. We also show that, for layered networks, a linear DMT of dmax(1-r)+between the maximum diversity dmaxand the maximum MG, rmax=1 is achievable. We adapt existing DMT optimal coding schemes to these networks, thus specifying the end-to-end communication strategy explicitly.

In this paper, the diversity-multiplexing gain tradeoff (DMT) of single-source, single-sink (ss-ss), multihop relay networks having slow-fading links is studied. In particular, the two end-points of the DMT of ss-ss full-duplex networks are determined, by showing that the maximum achievable diversity gain is equal to the min-cut and that the maximum multiplexing gain is equal to the min-cut rank, the latter by using an operational connection to a deterministic network. Also included in the paper, are several results that aid in the computation of the DMT of networks operating under amplify-and-forward (AF) protocols. In particular, it is shown that the colored noise encountered in amplify-and-forward protocols can be treated as white for the purpose of DMT computation, lower bounds on the DMT of lower-triangular channel matrices are derived and the DMT of parallel MIMO channels is computed. All protocols appearing in the paper are explicit and rely only upon AF relaying. Half-duplex networks and explicit coding schemes are studied in a companion paper.

Two key parameters in the outage characterization of a wireless fading network are the diversity and the degrees of freedom (DOF). These two quantities represent the two end-points of the diversity multiplexing gain tradeoff. In this paper, we present max-flow min-cut type theorems for computing both the diversity and the DOF of arbitrary single-source single-sink networks with nodes possessing multiple antennas. We also show that an amplify-and-forward protocol is sufficient to achieve the same. The DOF characterization is obtained using a conversion to a deterministic wireless network for which the capacity was recently found. This conversion is operational in the sense that a capacity-achieving scheme for the deterministic network can be converted into a DOF-achieving scheme for the fading network. We also show that the diversity result easily extends to multi-source multi-sink networks whereas the DOF result extends to a single-source multi-cast network. Along the way, we prove that the zero error capacity of the deterministic network is the same as its ∈-error capacity.

We consider single-source, single-sink multi-hop relay networks, with slow-fading Rayleigh fading links and single-antenna relay nodes operating under the half-duplex constraint.

We consider single-source, single-sink (ss-ss) multi-hop relay networks, with slow-fading Rayleigh links. This two-part paper aims at giving explicit protocols and codes to achieve the optimal diversity-multiplexing tradeoff (DMT) of two classes of multi-hop networks: K-parallel-path (KPP) networks and Layered networks.