Alexander Barg

Dr. Alexander Barg

orcid

Research Focus & Metrics

Academic Career Length

27Years (2000-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
30 January 2017 in IEEE Transactions on Information Theory
Verified
Journal Article
Open access
MYMin Ye
Min Ye
ABAlexander Barg
Alexander Barg
Maximum distance separable (MDS) codes are optimal error-correcting codes in the sense that they provide the maximum failure tolerance for a given number of parity nodes. Suppose that an MDS code with k information nodes and r = n - k parity nodes is used to encode data in a distributed storage system. It is known that if h out of the n nodes are inaccessible and d surviving (helper) nodes are used to recover the lost data, then we need to download at least h/(d + h - k) fraction of the data stored in each of the helper nodes (Dimakis et al., 2010 and Cadambe et al., 2013). If this lower bound is achieved for the repair of any h erased nodes from any d helper nodes, we say that the MDS code has the (h, d)-optimal repair property. We study high-rate MDS array codes with the optimal repair property (also known as minimum storage regenerating codes, or MSR codes). Explicit constructions of such codes in the literature are only available for the cases where there are at most three parity nodes, and these existing constructions can only optimally repair a single node failure by accessing all the surviving nodes. In this paper, given any r and n, we present two explicit constructions of MDS array codes with the (h, d)-optimal repair property for all h r and k d n - h simultaneously. Codes in the first family can be constructed over any base field F as long as |F| ≥ sn, where s = lcm(1, 2, . .. , r). The encoding, decoding, repair of failed nodes, and update procedures of these codes all have low complexity. Codes in the second family have the optimal access property and can be constructed over any base field F as long as |F| ≥ n+1. Moreover, both code families have the optimal error resilience capability when repairing failed nodes. We also construct several other related families of MDS codes with the optimal repair property.

26 February 2018 in IEEE Transactions on Information Theory
Verified
Journal Article
Closed access
MYMin Ye
Min Ye
ABAlexander Barg
Alexander Barg
We consider the minimax estimation problem of a discrete distribution with support size k under privacy constraints. A privatization scheme is applied to each raw sample independently, and we need to estimate the distribution of the raw samples from the privatized samples. A positive number ∈ measures the privacy level of a privatization scheme. For a given ∈, we consider the problem of constructing optimal privatization schemes with ∈-privacy level, i.e., schemes that minimize the expected estimation loss for the worst-case distribution. Two schemes known in the literature provide order optimal performance in the high privacy regime where E is very close to 0, and in the low privacy regime where e ∈ ≈ k, respectively. In this paper, we propose a new family of schemes which substantially improve the performance of the existing schemes in the medium privacy regime when 1 ≪ e ∈ ≪ k. More concretely, we prove that when 3.8 <; ∈ <; ln(k/9), our schemes reduce the expected estimation loss by 50% under ℓ 2 2 metric and by 30% under ℓ 1 metric over the existing schemes. We also prove a lower bound for the region e ∈ ≪ k, which implies that our schemes are order optimal in this regime.

24 July 2017 in IEEE Transactions on Information Theory
Verified
Journal Article
Open access
MYMin Ye
Min Ye
ABAlexander Barg
Alexander Barg
An (n, k, l) maximum distance separable (MDS) array code of length n, dimension k = n - r, and subpacketization l is formed of l × n matrices over a finite field F, with every column of the matrix stored on a separate node in the distributed storage system and viewed as a coordinate of the codeword. Repair of a failed node (recovery of one erased column) can be performed by accessing a set of d ≤ n - 1 surviving (helper) nodes. The code is said to have the optimal access property if the amount of data accessed at each of the helper nodes meets a lower bound on this quantity. For optimal-access MDS codes with d = n-1, the sub-packetization l satisfies the bound l ≥ r (k-1)/r . In our previous work (IEEE Trans. Inf. Theory, vol. 63, no. 4, 2017), for any n and r, we presented an explicit construction of optimal-access MDS codes with subpacketization l = r ⌈n-1⌉ . In this paper, we take up the question of reducing the sub-packetization value l to make it to approach the lower bound. We construct an explicit family of optimal-access codes with l = r1.n/rl, which differs from the optimal value by at most a factor of r 2 . These codes can be constructed over any finite field F as long as |F| ≥ r⌈n/r⌉, and afford low-complexity encoding and decoding procedures. We also define a version of the repair problem that bridges the context of regenerating codes and codes with locality constraints (LRC codes), which we call group repair with optimal access. In this variation, we assume that the set of n = sm nodes is partitioned into m repair groups of size s, and require that the amount of accessed data for repair is the smallest possible whenever the d = s + k - 1 helper nodes include all the other s-1 nodes from the same group as the failed node. For this problem, we construct a family of codes with the group optimal access property. These codes can be constructed over any field F of size |F| ≥ n, and also afford low-complexity encoding and decoding procedures.

3 May 2017 in IEEE Transactions on Information Theory
Verified
Journal Article
Open access
ABAlexander Barg
Alexander Barg
ITItzhak Tamo
Itzhak Tamo
SVSerge Vladut
Serge Vladut
A code over a finite alphabet is called locally recoverable (LRC code) if every symbol in the encoding is a function of a small number (at most r) of other symbols of the codeword. In this paper, we introduce a construction of LRC codes on algebraic curves, extending a recent construction of the Reed-Solomon like codes with locality. We treat the following situations: local recovery of a single erasure, local recovery of multiple erasures, and codes with several disjoint recovery sets for every coordinate (the availability problem). For each of these three problems we describe a general construction of codes on curves and construct several families of LRC codes. We also describe a construction of codes with availability that relies on automorphism groups of curves. We also consider the asymptotic problem for the parameters of the LRC codes on curves. We show that the codes obtained from asymptotically maximal curves (for instance, Garcia-Stichtenoth towers) improve upon the asymptotic versions of the Gilbert-Varshamov bound for LRC codes.

31 January 2018 in IEEE Transactions on Information Theory
Verified
Journal Article
Closed access
AAAbhishek Agarwal
Abhishek Agarwal
ABAlexander Barg
Alexander Barg
SHSihuang Hu
Sihuang Hu
AMArya Mazumdar
Arya Mazumdar
ITItzhak Tamo
Itzhak Tamo
Locally recoverable (LRC) codes have recently been a focus point of research in coding theory due to their theoretical appeal and applications in distributed storage systems. In an LRC code, any erased symbol of a codeword can be recovered by accessing only a small number of other symbols. For LRC codes over a small alphabet (such as binary), the optimal rate-distance trade-off is unknown. We present several new combinatorial bounds on LRC codes including the locality-aware sphere packing and Plotkin bounds. We also develop an approach to linear programming (LP) bounds on LRC codes. The resulting LP bound gives better estimates in examples than the other upper bounds known in the literature. Further, we provide the tightest known upper bound on the rate of linear LRC codes with a given relative distance, an improvement over the previous best known bounds.

16 September 2019 in IEEE Transactions on Information Theory
Verified
Journal Article
Closed access
ZCZitan Chen
Zitan Chen
ABAlexander Barg
Alexander Barg
The paper is devoted to the problem of erasure coding in distributed storage. We consider a model of storage that assumes that nodes are organized into equally sized groups, called racks, that within each group the nodes can communicate freely without taxing the system bandwidth, and that the only information transmission that counts is the one between the racks. This assumption implies that the nodes within each of the racks can collaborate before providing information to the failed node. The main emphasis of the paper is on code construction for this storage model. We present an explicit family of maximum distance separable (MDS) array codes that support recovery of a single failed node from any number of helper racks using the minimum possible amount of inter-rack communication(such codes are said to provide optimal repair). The codes are constructed over finite fields of size comparable to the code length. We also derive a bound on the number of symbols accessed at helper nodes for the purposes of repair, and construct a code family that approaches this bound, while still maintaining the optimal repair property. Finally, we present a construction of scalar Reed-Solomon codes that support optimal repair for the rack-oriented storage model.