Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userExplicit MSR Codes with Optimal Access, Optimal Sub-Packetization and Small Field Size for $d = k+1, k+2, k+3$
567
0
0.0
(
0
)
Added by
Myna Vajha
Publication date
2018
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
This paper presents the construction of an explicit, optimal-access, high-rate MSR code for any $(n,k,d=k+1,k+2,k+3)$ parameters over the finite field $fQ$ having sub-packetization $alpha = q^{lceilfrac{n}{q}rceil}$, where $q=d-k+1$ and $Q = O(n)$. The sub-packetization of the current construction meets the lower bound proven in a recent work by Balaji et al. in cite{BalKum}. To our understanding the codes presented in this paper are the first explicit constructions of MSR codes with $d<(n-1)$ having optimal sub-packetization, optimal access and small field size.
rate research
Read More
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 ge 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 ge 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.
An $(n, M)$ vector code $mathcal{C} subseteq mathbb{F}^n$ is a collection of $M$ codewords where $n$ elements (from the field $mathbb{F}$) in each of the codewords are referred to as code blocks. Assuming that $mathbb{F} cong mathbb{B}^{ell}$, the code blocks are treated as $ell$-length vectors over the base field $mathbb{B}$. Equivalently, the code is said to have the sub-packetization level $ell$. This paper addresses the problem of constructing MDS vector codes which enable exact reconstruction of each code block by downloading small amount of information from the remaining code blocks. The repair bandwidth of a code measures the information flow from the remaining code blocks during the reconstruction of a single code block. This problem naturally arises in the context of distributed storage systems as the node repair problem [4]. Assuming that $M = |mathbb{B}|^{kell}$, the repair bandwidth of an MDS vector code is lower bounded by $big(frac{n - 1}{n - k}big)cdot ell$ symbols (over the base field $mathbb{B}$) which is also referred to as the cut-set bound [4]. For all values of $n$ and $k$, the MDS vector codes that attain the cut-set bound with the sub-packetization level $ell = (n-k)^{lceil{{n}/{(n-k)}}rceil}$ are known in the literature [23, 35]. This paper presents a construction for MDS vector codes which simultaneously ensures both small repair bandwidth and small sub-packetization level. The obtained codes have the smallest possible sub-packetization level $ell = O(n - k)$ for an MDS vector code and the repair bandwidth which is at most twice the cut-set bound. The paper then generalizes this code construction so that the repair bandwidth of the obtained codes approach the cut-set bound at the cost of increased sub-packetization level. The constructions presented in this paper give MDS vector codes which are linear over the base field $mathbb{B}$.
This paper addresses the problem of constructing MDS codes that enable exact repair of each code block with small repair bandwidth, which refers to the total amount of information flow from the remaining code blocks during the repair process. This problem naturally arises in the context of distributed storage systems as the node repair problem [7]. The constructions of exact-repairable MDS codes with optimal repair-bandwidth require working with large sub-packetization levels, which restricts their employment in practice. This paper presents constructions for MDS codes that simultaneously provide both small repair bandwidth and small sub-packetization level. In particular, this paper presents two general approaches to construct exact-repairable MDS codes that aim at significantly reducing the required sub-packetization level at the cost of slightly sub-optimal repair bandwidth. The first approach gives MDS codes that have repair bandwidth at most twice the optimal repair-bandwidth. Additionally, these codes also have the smallest possible sub-packetization level $ell = O(r)$, where $r$ denotes the number of parity blocks. This approach is then generalized to design codes that have their repair bandwidth approaching the optimal repair-bandwidth at the cost of graceful increment in the required sub-packetization level. The second approach transforms an MDS code with optimal repair-bandwidth and large sub-packetization level into a longer MDS code with small sub-packetization level and near-optimal repair bandwidth. For a given $r$, the obtained codes have their sub-packetization level scaling logarithmically with the code length. In addition, the obtained codes require field size only linear in the code length and ensure load balancing among the intact code blocks in terms of the information downloaded from these blocks during the exact reconstruction of a code block.
We construct maximally recoverable codes (corresponding to partial MDS codes) which are based on linearized Reed-Solomon codes. The new codes have a smaller field size requirement compared with known constructions. For certain asymptotic regimes, the constructed codes have order-optimal alphabet size, asymptotically matching the known lower bound.
We consider multi-access coded caching problem introduced by Hachem et.al., where each user has access to $L$ neighboring caches in a cyclic wrap-around fashion. We focus on the deterministic schemes for a specific class of multi-access coded caching problem based on the concept of PDA. We construct new PDAs which specify the delivery scheme for the specific class of multi-access coded caching problem discussed in this paper. For the proposed scheme, the coding gain is larger than that of the state-of-the-art while the sub-packetization level varies only linearly with the number of users. Hence, we achieve a lower transmission rate with the least sub-packetization level compared to the existing schemes.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
