In large-scale distributed storage systems, erasure coding is employed to ensure reliability against disk failures. Recent work by Kadekodi et al. demonstrates that adapting code parameters to varying disk failure rates can lead to significant storage savings without compromising reliability. Such adaptations, known ascode conversions, motivate the design ofconvertible codes, which enable efficient transformations between codes of different parameters. In this work, we study the setting in which λ codewords of an initial [nI=kI+rI,kI] MDS code are merged into a single codeword of a final [nF= λkI+rF,kF= λkI] MDS code. We begin by presenting three constructions that achieve optimalaccess cost, defined as the total number of disks accessed during the conversion process. The first two constructions apply when λ ≤rIand impose specific divisibility conditions onrIand the field sizeq. These schemes minimize both the per-symbol and the overall access cost. The third construction, which builds on a prior scheme by Kong, achieves minimal access cost while supporting arbitrary parameter regimes. All three constructions require field sizes that are linear in the final code length, and notably, the third construction achieves a field size that matches the lower bound implied by the MDS conjecture in almost all cases. In addition, we propose a construction that optimizes thebandwidth cost, defined as the total number of symbols transmitted during conversion. This scheme is a refinement of Maturana and Rashmi’s bandwidth-optimal construction based on the piggybacking framework, and achieves reduced sub-packetization.The code will be available at https://github.com/ZhilongNiu/SDMoMFE.

In large-scale distributed storage systems, erasure coding provides reliability against disk failures. Recent work by Kadekodi et al. demonstrates that adapting code parameters to varying disk failure rates can lead to storage savings, without compromising reliability. During such adaptations (also called code conversions), data encoded with multiple codewords of an initial [$n^{I}, k^{I}$] code are transformed into multiple codewords of a final$\left[n^{F}, k^{F}\right]$code. The convertible codes framework aims to design initial and final codes to enable resource-efficient conversions. In this paper, we study the scenario where$\lambda \geq 2$codewords of an initial$\left[n^{I}=k^{I}+r^{I}, k^{I}\right]$MDS code are merged into a single codeword of a final$\left[n^{F}=\lambda k^{I}+r^{F}, k^{F}=\lambda k^{I}\right]$MDS code. Some initial code symbols are retained in the final codeword, while others are newly generated. The access cost is the total number of symbols read or written during the conversion procedure to produce new symbols. In this paper, we present three convertible code constructions. The first two require$\lambda \leq r^{I}$and impose certain divisibility conditions on$r^{I}$and the field size$q$. However, they minimize the access cost incurred for generating each new symbol individually and for all symbols cumulatively. The third construction, a modification of an earlier construction by Kong, minimizes the cumulative access cost and works for all parameters. All the code constructions require field sizes linear in the block length of the final code and achieve the smallest known field sizes across MDS convertible codes in the literature.

Streaming codes are packet-level codes designed to ensure the timely recovery of lost packets. This paper focuses on streaming codes for multi-hop relay networks that guarantee the recovery of message packets within a delay of$\tau$time slots, even when a burst erasure affecting at most$b$packets occurs on each link. We first present a straightforward upper bound on the rate of burst-erasure-correcting streaming codes for multi-hop relay networks. The main contribution of this paper is a coding scheme that achieves rates arbitrarily close to this rate upper bound as the message size increases.

We study burst erasure correcting streaming codes for three-node relay networks, where there is a source-relay link and a relay-destination link. These codes guarantee that all message packets are recovered within a delay of$\tau $time slots, given that a single burst erasure of length at most b packets occurs in both links. Leveraging previously known techniques in the streaming code literature, we first provide a simple upper bound on the rate of burst erasure correcting streaming codes for three-node relay networks. Our main result is a coding scheme that achieves rates arbitrarily close to the rate upper bound, as message size increases.

We study burst erasure correcting streaming codes for three-node relay networks, where there is a source-relay link and a relay-destination link. These codes guarantee that all message packets are recovered within a delay of$\tau$time slots, given that a single burst erasure of length at most$b$packets occurs in both links. Leveraging previously known techniques in the streaming code literature, we first provide a simple upper bound on the rate of burst erasure correcting streaming codes for three-node relay networks. Our main result is a coding scheme that achieves rates arbitrarily close to the rate upper bound as message size increases.

Streaming codes are a class of packet-level erasure codes that ensure packet recovery over a sliding window channel which allows either a burst erasure of size$b$or$a$random erasures within any window of size$(\tau +1)$time units, under a strict decoding-delay constraint$\tau $. The field size over which streaming codes are constructed is an important factor in determining the implementation complexity. The best-known explicit rate-optimal streaming code, which covers all$\{a,b,\tau \}$parameter choices, requires a field size of$q^{2}$, where$q \ge \tau +b-a$is a prime power. In this work, we present an explicit rate-optimal streaming code over a field of size$q^{2}$, for prime power$q \ge \tau $. This is the smallest known field size for an explicit rate-optimal construction that takes into account all$\{a,b,\tau \}$parameters. We achieve this by modifying the non-explicit code construction due to Krishnan et al., without changing the field size. We also present a generalization of our construction, which results in streaming codes over further smaller fields by trading off code rate.

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.

For a convolutional code in the presence of a symbol erasure channel, the information debt I(t) at time t provides a measure of the number of additional code symbols required to recover all message symbols up to time t. Information-debt-optimal streaming (iDOS) codes are convolutional codes which allow for the recovery of all message symbols up to t whenever I(t) turns zero under the following conditions; (i) information debt can be non-zero for at most τ consecutive time slots and (ii) information debt never increases beyond a particular threshold. The existence of periodically-time-varying iDOS codes are known for all parameters. In this paper, we address the problem of constructing explicit, time-invariant iDOS codes. We present an explicit time-invariant construction of iDOS codes for the unit memory (m = 1) case. It is also shown that a construction method for convolutional codes due to Almeida et al. leads to explicit time-invariant iDOS codes for all parameters. However, this general construction requires a larger field size than the first construction for the m = 1 case.

This paper investigates adaptive streaming codes over a three-node relayed network. In this setting, a source node transmits a sequence of message packets to a destination with help of a relay. The source-to-relay and relay-to-destination links are unreliable and introduce at most$N_{1}$and$N_{2}$packet erasures, respectively. The destination node must recover each message packet within a strict delay constraint$T$. The paper presents a new construction of streaming codes for all feasible parameters$\{N_{1}, N_{2}, T\}$. Our work improves upon the construction in Fong et al. by adapting the relaying strategy based on the erasure patterns from source to relay. Specifically, the code employs the notion of symbol estimates, which allows the relay to forward information about symbols before it can decode that symbol, and variable-rate encoding, which decreases the rate used to encode a packet as more erasures affect that packet. The codes proposed in this paper achieve rates higher than the ones proposed by Fong et al. whenever$N_{2} > N_{1}$, and achieve the same rate when$N_{2} \leq N_{1}$, in which case the rate is optimal. The paper also presents an upper bound on the achievable rate that takes into account erasures in both links in order to bound the rate in the second link. The upper bound is shown to be tighter than a trivial bound that considers only the erasures in the second link.

This paper investigates low-latency adaptive streaming codes for a three-node relay network. A source node transmits a sequence of source packets (messages) to the destination through a relay node. We focus on a particular case where the link connecting the source and relay nodes is almost reliable, but the link connecting the relay to the destination is not. The relay node can observe the erasure pattern that has occurred in the transmission between the source node and itself and adapt its relaying strategy based on that observation. Every source packet must be perfectly recovered by the destination with a strict delay T, as long as the number of erasures in the relay-to-destination link lies below some design parameter. We then characterize capacity as a function of such design parameter. The achievability scheme employs two different relaying strategies, based on whether an erasure has or has not occurred in the link from source to relay. The converse is proven by analyzing a periodic erasure pattern and lower bounding the minimum redundancy across channel packets. We show that the achievable rate can be improved compared to non-adaptive schemes previously proposed, indicating that exploiting the knowledge of the erasure pattern by the relay node is essential in achieving capacity.

In the context of an (n,k,m) convolutional code where k is the number of message symbols, n the number of code symbols and m the memory, Martinian [1] introduced the concept of information debt whose value at time t is the number of additional coded symbols needed to decode all prior message symbols. The same paper shows the existence of (n,k,m) convolutional codes that can recover all prior message symbols whenever the symbol-erasure pattern is such that the maximum time interval τ between successive returns to zero of the information debt function is at most m. The parameter τ also represents the worst-case delay in decoding a message symbol. In the present paper, we study (n,k,m) convolutional codes that possess the analogous property for the case τ > m whenever it is possible to do so. We will refer to such codes as information-debt-optimal streaming (iDOS) codes. We prove the existence of periodically time-varying iDOS codes for all possible {n,k,m,τ} parameters. We also show that m-MDS codes and Maximum Distance Profile convolutional codes are iDOS codes for certain parameter ranges. As a by-product of our existence result, the minimum memory needed for a particular class of streaming codes studied earlier in the literature, is determined.

Streaming codes are a class of packet-level erasure codes that ensure packet recovery over a sliding window channel which allows either a burst erasure of size$b$or$a$random erasures within any window of size ($\tau+1$) time units, under a strict decoding-delay constraint$\tau$. The field size over which streaming codes are constructed is an important factor determining the complexity of implementation. The best known explicit rate-optimal streaming code requires a field size of$q^{2}$where$q\geq\tau+b-a$is a prime power. In this work, we present an explicit rate-optimal streaming code, for all possible$\{a, b,\tau\}$parameters, over a field of size$q^{2}$for prime power$q\geq \tau$. This is the smallest-known field size of a general explicit rate-optimal construction that covers all$\{a, b, \tau\}$parameter sets. We achieve this by modifying the non-explicit code construction due to Krishnan et al. to make it explicit, without change in field size.

In this paper, we investigate streaming codes over a three-node relay network. Source node transmits a sequence of message packets to the destination via a relay. Source-to-relay and relay-to-destination links are unreliable and introduce at most N1and N2packet erasures, respectively. Destination needs to recover each message packet with a strict decoding delay constraint of T time slots. We propose streaming codes under this setting for all feasible parameters $\{N_{1},\ N_{2},\ T\}$. Relay naturally observes erasure patterns occurring in the source-to-relay link. In our code construction, we employ a channel-state-dependent relaying strategy, which rely on these observations. In a recent work, Fong et al. provide streaming codes featuring channel-state-independent relaying strategies, for all feasible parameters $\{N_{1},\ N_{2},\ T\}$. Our schemes offer a strict rate improvement over the schemes proposed by Fong et al., whenever $N_{1}\lt N_{2}$.

An (a, b, τ) streaming code is a packet-level erasure code that can recover under a strict delay constraint of τ time units, from either a burst of b erasures or else of a random erasures, occurring within a sliding window of time duration w. While rate-optimal constructions of such streaming codes are available for all parameters {a, b, τ, w} in the literature, they require in most instances, a quadratic, O(τ2) field size. In this work, we make further progress towards field size reduction and present rate-optimal O(τ) field size streaming codes for two regimes: (i) gcd(b, τ + 1 - a) ≥ a (ii) τ + 1 a + b and b mod a ϵ 0, a - 1.

In this work, we consider a sequence of $J$ matrix multiplication jobs which needs to be distributed by a master across multiple worker nodes. For $i\in \{1,2,\ldots,J\}$, job-$i$ begins in round-$i$ and has to be completed by round-$(i+T)$. Previous works consider only the special case of $T=0$ and focus on coding across workers. We propose here two schemes with $T>0$, which feature coding across workers as well as the dimension of time. Our first scheme is a modification of the polynomial coding scheme introduced by Yu et al. and places no assumptions on the straggler model. Exploitation of the temporal dimension helps the scheme handle a larger set of straggler patterns than the polynomial coding scheme, for a given computational load per worker per round. The second scheme assumes a particular straggler model to further improve performance (in terms of encoding/decoding complexity). We develop theoretical results establishing (i) optimality of our proposed schemes for a certain class of straggler patterns and (ii) improved performance for the case of i.i.d. stragglers. These are further validated by experiments, where we implement our schemes to train neural networks.

In this paper, we design erasure-correcting codes for channels with burst and random erasures, when a strict decoding delay constraint is in place. We consider the sliding-window-based packet erasure model proposed by Badr et al., where any time-window of width w contains either up to a random erasures or an erasure burst of length at most b. One needs to recover any erased packet with a strict decoding delay deadline of τ, where erasures are as per the channel model. Presently existing rate-optimal constructions in the literature require, in general, a field-size which grows exponential in τ, as long as a/τ remains a constant. In this work, we present a new rate-optimal code construction covering all channel and delay parameters, which requires an O(τ2) field-size. As a special case, when (b - a) = 1, we have a field-size linear in τ. We also present two other constructions having linear fieldsize, under certain constraints on channel and decoding delay parameters. As a corollary, we obtain low field-size, rate-optimal convolutional codes for any given column distance and column span. Simulations indicate that the newly proposed streaming code constructions offer lower packet-loss probabilities compared to existing schemes, for selected instances of Gilbert-Elliott and Fritchman channels.

We study the problem of designing error-correcting codes over channels with burst and random erasures, when a strict decoding delay constraint τ is in place. Badr et al. introduced a channel model wherein for any sliding-window of width w, at most one of the following erasures patterns are permissible; (i) a burst erasure of length ≤ b or (ii) a total of ≤ a random erasures. We present a rate-optimal code construction under this model, which covers all feasible channel and delay parameters. In contrast to existing rate-optimal code families which require a field-size at least as large as O((τα)), our a construction needs a field-size quadratic in the decoding delay constraint. For some parameters, the construction can be over linear field-size.

Recovery of data packets from packet erasures in a timely manner is critical for many streaming applications. An early paper by Martinian and Sundberg introduced a framework for streaming codes and designed rate-optimal codes that permit delay-constrained recovery from an erasure burst of length up to B. A recent work by Badr et al. extended this result and introduced a sliding-window channel model C(N, B, W). Under this model, in a sliding-window of width W, one of the following erasure patterns are possible (i) a burst of length at most B or (ii) at most N (possibly non-contiguous) arbitrary erasures. Badr et al. obtained a rate upper bound for streaming codes that can recover with a time delay T, from any erasure patterns permissible under the C(N, B, W) model. However, constructions matching the bound were absent, except for a few parameter sets. In this paper, we present a family of codes that achieves the rate upper bound for all feasible parameters N, B, W and T.

In this paper, we study vector codes with all-symbol locality, where the local code is either a Minimum Bandwidth Regenerating (MBR) code or a Minimum Storage Regenerating (MSR) code. In the first part, we present vector codes with all-symbol MBR locality, for all parameters, that have both optimal minimum-distance and optimal rate. These codes combine ideas from two popular codes in the distributed storage literature; Product-Matrix codes and Tamo-Barg codes. In the second part which deals with codes having all-symbol MSR locality, we follow a Pairwise Coupling Transform-based approach to arrive at optimal minimum-distance and optimal rate, for a range of parameters. All the code constructions presented in this paper have a low field-size that grows linearly with the code-length n.

In this paper, we show how the presence of locality within a binary cyclic code can be exploited to improve decoding performance and to reduce decoding complexity. We pursue two approaches. Under the first approach, we show how the ordered statistics decoding (OSD) method can be modified by inserting a simple single round belief-propagation step at the start that involves only the local codes. The resultant locality-aware OSD algorithm yields an appreciable signal-to-noise ratio (SNR) gain for a given level of reliability and essentially the same level of decoder complexity. Under the second, trellis decoding approach, we show that the careful introduction of locality results in the creation of a cyclic subcode that possesses lower maximum state complexity. In addition, we present a simple means of deriving an upper bound to the state complexity profile of any cyclic code that is based only on the zeros of the code. Furthermore, we show how the decoding speed of either locality-aware OSD or trellis decoding can be significantly increased in the presence of locality, in the moderate-to-high SNR regime, by making the use of a quick-look decoder that often returns the maximum likelihood code word.

In this paper, we study the impact of locality on the decoding of binary cyclic codes under two approaches, namely ordered statistics decoding (OSD) and trellis decoding. Given a binary cyclic code having locality or availability, we suitably modify the OSD to obtain gains in terms of Signal-To-Noise ratio, for a given reliability and essentially the same level of decoder complexity. With regard to trellis decoding, we show that careful introduction of locality results in the creation of cyclic subcodes having lower maximum state complexity. We also present a simple upper-bounding technique on the state complexity profile, based on the zeros of the code. Finally, it is shown how the decoding speed can significantly be increased in the presence of locality, in the moderate-to-high SNR regime, by making use of a quick-look decoder that often returns the ML codeword.

An early paper by Rashmi et al. presented the construction of an (n, k, d = n - 1) MBR regenerating code featuring the inherent double replication of all code symbols and repair-by-transfer (RBT), both of which are important in practice. We first show that no MBR code can contain even a single code symbol that is replicated more than twice. We then go on to present two new families of MBR codes which feature double replication of all systematic message symbols. The codes also possess a set of d nodes whose contents include the message symbols and which can be repaired through help-by-transfer (HBT). As a corollary, we obtain systematic RBT codes for the case d = (n - 1) that possess inherent double replication of all code symbols and having a field size of O(n) in comparison with the general, O(n2) field size requirement of the earlier construction by Rashmi et al. For the cases (k = d = n - 2) or (k + 1 = d = n - 2), the field size can be reduced to q = 2, and hence the codes can be binary. We also give a necessary and sufficient condition for the existence of MBR codes having double replication of all code symbols and also suggest techniques which will enable an arbitrary MBR code to be converted to one with double replication of all code symbols.

In this paper, we consider the setting of exact repair linear regenerating codes. Under this setting, we derive a new outer bound on the storage-repair-bandwidth trade-off for the case when d = k = n - 1, where (n; k; d) are parameters of the regenerating code, with their usual meaning. Taken together with the achievability result of Tian et. al. [1], we show that the new outer bound derived here completely characterizes the tradeoff for the case of exact repair linear regenerating codes, when d = k = n-1. The new outer bound is derived by analyzing the dual code of the linear regenerating code.