Source author record

Zhifang Zhang

Zhifang Zhang appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Information Theory math.IT

Catalog footprint

What is connected

10works

2topics

3close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2022arXiv

An Efficient Piggybacking Design Framework with Sub-packetization $l\le r$ for All-Node Repair

Piggybacking design has been widely applied in distributed storage systems since it can greatly reduce the repair bandwidth with small sub-packetization. Compared with other existing erasure codes, piggybacking is more convenient to operate and the I/O cost is lower. In this paper, we propose a new efficient design which can further reduce the repair bandwidth with the sub-packetization $l\le r$ where $r = n-k$. Generally, we let $l\le 8$. Compared with other analogous designs, our design has lower $l$ and the value of $l$ is more flexible. Moreover, our design can repair all nodes with small repair bandwidth. Therefore our piggybacking design is more feasible.

preprint2022arXiv

Rack-Aware Regenerating Codes with Multiple Erasure Tolerance

In a modern distributed storage system, storage nodes are organized in racks, and the cross-rack communication dominates the system bandwidth. In We study the rack-aware storage system where all storage nodes are organized in racks and within each rack the nodes can communicate freely without taxing the system bandwidth. Rack-aware regenerating codes (RRCs) were proposed for minimizing the repair bandwidth for single erasures. In the initial setting of RRCs, the repair of a single node requires the participation of all the remaining nodes in the rack containing the failed node as well as a large number of helper racks containing no failures. Consequently, the repair may be infeasible in front of multiple node failures. In this work, a relaxed repair model that can tolerate multiple node failures by simultaneously reducing the intra-rack connections and cross-rack connections is proposed. A tradeoff between the storage and repair bandwidth under the relaxed repair model is derived, and parameters of the two extreme points on the tradeoff curve are characterized for the minimum storage and minimum bandwidth respectively. Moreover, two codes corresponding to the extreme points are explicitly constructed over the fields of size comparable to the code length and with the lowest sub-packetization. Finally, for the convenience of practical use, systematic encoding processes for the two codes are also established.

preprint2021arXiv

Explicit Construction of Minimum Bandwidth Rack-Aware Regenerating Codes

In large data centers, storage nodes are organized in racks, and the cross-rack transmission dominates the bandwidth cost. For the repair of single node failures, codes achieving the tradeoff between the storage redundancy and cross-rack repair bandwidth are called rack-aware regenerating codes (RRCs). In this work, we give the first explicit construction of RRCs with the minimum repair bandwidth (i.e., the cross-rack bandwidth equals the storage size per node). Our construction applies to all admissible parameters and has the lowest sub-packetization level. Moreover, the underlying finite fields are of size comparable to the number of storage nodes, which makes our codes more implementable in practice. Finally, for the convenience of practical use, we also establish a transformation to convert our codes into systematic codes.

preprint2021arXiv

Rack-Aware Regenerating Codes with Fewer Helper Racks

We consider the rack-aware storage system where $n$ nodes are organized in $\bar{n}$ racks each containing $u$ nodes, and any $k$ nodes can retrieve the stored file. Moreover, any single node erasure can be recovered by downloading data from $\bar{d}$ helper racks as well as the remaining $u\!-\!1$ nodes in the same rack. Previous work mostly focuses on minimizing the cross-rack repair bandwidth under the condition $\bar{d}\geq \bar{k}$, where $\bar{k}=\lfloor\frac{k}{u}\rfloor$. However, $\bar{d}\geq \bar{k}$ is not an intrinsic condition for the rack-aware storage model. In this paper, we establish a tradeoff between the storage overhead and cross-rack repair bandwidth for the particularly interesting case $\bar{d}\!<\!\bar{k}$. Furthermore, we present explicit constructions of codes with parameters lying on the tradeoff curve respectively at the minimum storage point and minimum bandwidth point. The codes are scalar or have sub-packetization $\bar{d}$, and operate over finite fields of size comparable to $n$. Regarding $\bar{d}$ as the repair degree, these codes combine the advantage of regenerating codes in minimizing the repair bandwidth and that of locally repairable codes in reducing the repair degree. Moreover, they also abandon the restriction of MBR codes having storage overhead no less than $2\times$ and that of high-rate MSR codes having exponential sub-packetization level.

preprint2015arXiv

Achieving Arbitrary Locality and Availability in Binary Codes

The $i$th coordinate of an $(n,k)$ code is said to have locality $r$ and availability $t$ if there exist $t$ disjoint groups, each containing at most $r$ other coordinates that can together recover the value of the $i$th coordinate. This property is particularly useful for codes for distributed storage systems because it permits local repair and parallel accesses of hot data. In this paper, for any positive integers $r$ and $t$, we construct a binary linear code of length $\binom{r+t}{t}$ which has locality $r$ and availability $t$ for all coordinates. The information rate of this code attains $\frac{r}{r+t}$, which is always higher than that of the direct product code, the only known construction that can achieve arbitrary locality and availability.

preprint2014arXiv

An Integer Programming Based Bound for Locally Repairable Codes

The locally repairable code (LRC) studied in this paper is an $[n,k]$ linear code of which the value at each coordinate can be recovered by a linear combination of at most $r$ other coordinates. The central problem in this work is to determine the largest possible minimum distance for LRCs. First, an integer programming based upper bound is derived for any LRC. Then by solving the programming problem under certain conditions, an explicit upper bound is obtained for LRCs with parameters $n_1>n_2$, where $n_1 = \left\lceil \frac{n}{r+1} \right\rceil$ and $n_2 = n_1 (r+1) - n$. Finally, an explicit construction for LRCs attaining this upper bound is presented over the finite field $\mathbb{F}_{2^m}$, where $m\geq n_1r$. Based on these results, the largest possible minimum distance for all LRCs with $r \le \sqrt{n}-1$ has been definitely determined, which is of great significance in practical use.

preprint2014arXiv

Repair Locality From a Combinatorial Perspective

Repair locality is a desirable property for erasure codes in distributed storage systems. Recently, different structures of local repair groups have been proposed in the definitions of repair locality. In this paper, the concept of regenerating set is introduced to characterize the local repair groups. A definition of locality $r^{(δ-1)}$ (i.e., locality $r$ with repair tolerance $δ-1$) under the most general structure of regenerating sets is given. All previously studied locality turns out to be special cases of this definition. Furthermore, three representative concepts of locality proposed before are reinvestigated under the framework of regenerating sets, and their respective upper bounds on the minimum distance are reproved in a uniform and brief form. Additionally, a more precise distance bound is derived for the square code which is a class of linear codes with locality $r^{(2)}$ and high information rate, and an explicit code construction attaining the optimal distance bound is obtained.

preprint2013arXiv

Repair Locality with Multiple Erasure Tolerance

In distributed storage systems, erasure codes with locality $r$ is preferred because a coordinate can be recovered by accessing at most $r$ other coordinates which in turn greatly reduces the disk I/O complexity for small $r$. However, the local repair may be ineffective when some of the $r$ coordinates accessed for recovery are also erased. To overcome this problem, we propose the $(r,δ)_c$-locality providing $δ-1$ local repair options for a coordinate. Consequently, the repair locality $r$ can tolerate $δ-1$ erasures in total. We derive an upper bound on the minimum distance $d$ for any linear $[n,k]$ code with information $(r,δ)_c$-locality. For general parameters, we prove existence of the codes that attain this bound when $n\geq k(r(δ-1)+1)$, implying tightness of this bound. Although the locality $(r,δ)$ defined by Prakash et al provides the same level of locality and local repair tolerance as our definition, codes with $(r,δ)_c$-locality are proved to have more advantage in the minimum distance. In particular, we construct a class of codes with all symbol $(r,δ)_c$-locality where the gain in minimum distance is $Ω(\sqrt{r})$ and the information rate is close to 1.

preprint2012arXiv

Exact Cooperative Regenerating Codes with Minimum-Repair-Bandwidth for Distributed Storage

We give an explicit construction of exact cooperative regenerating codes at the MBCR (minimum bandwidth cooperative regeneration) point. Before the paper, the only known explicit MBCR code is given with parameters $n=d+r$ and $d=k$, while our construction applies to all possible values of $n,k,d,r$. The code has a brief expression in the polynomial form and the data reconstruction is accomplished by bivariate polynomial interpolation. It is a scalar code and operates over a finite field of size $q\geq n$. Besides, we establish several subspace properties for linear exact MBCR codes. Based on these properties we prove that linear exact MBCR codes cannot achieve repair-by-transfer.

preprint2012arXiv

Network Coding Based on Chinese Remainder Theorem

Random linear network code has to sacrifice part of bandwidth to transfer the coding vectors, thus a head of size k log|T| is appended to each packet. We present a distributed random network coding approach based on the Chinese remainder theorem for general multicast networks. It uses a couple of modulus as the head, thus reduces the size of head to O(log k). This makes it more suitable for scenarios where the number of source nodes is large and the bandwidth is limited. We estimate the multicast rate and show it is satisfactory in performance for randomly designed networks.

Institution

Affiliation not imported yet

This author record came from a source that does not expose affiliation metadata. Once the author claims the profile or we enrich the record from another provider, this section will link to the concrete institution.

Topic footprint