Search

A primary objective of a distributed storage system is to reliably store huge amounts of source data for long periods of time using a large number of high storage capacity nodes. Storage nodes are prone to permanent failures, where such node failures cause all stored data to be permanently lost, and failed nodes are replaced with nodes that initially store no data. To maintain recoverability of the source data as storage nodes fail and are replaced, a total amount of storage capacity that is larger than the source data size is allocated to store the source data, and a repairer continually reads data from and writes data to the storage nodes as they fail and are replaced. We prove information-theoretic lower bounds on the rate at which a repairer reads data from the storage system as a function of the rate at which nodes fail and the amount by which the allocated storage capacity exceeds the source data size. These lower bounds hold for any repairer, i.e., any repairer that does not read data at or above the lower bound rate will provably not maintain recoverability of the source data. The bounds are provably tight asymptotically as the number of storage nodes grows and the allocated storage capacity approaches the source data size. [ABSTRACT FROM AUTHOR]

Let $\mathbb {F}_{q}$ be the finite field of $q$ elements. In this paper we obtain bounds on the following counting problem: given a polynomial $f(x)\in \mathbb {F}_{q} [x]$ of degree $k+m$ and a non-negative integer $r$ , count the number of polynomials $g(x)\in \mathbb {F}_{q} [x]$ of degree at most $k-1$ such that $f(x)+g(x)$ has exactly $r$ roots in $\mathbb {F}_{q}$. Previously, explicit formulas were known only for the cases $m=0, 1, 2$. As an application, we obtain an asymptotic formula on the list size of the standard Reed-Solomon code $[q, k, q-k+1]_{q}$. [ABSTRACT FROM AUTHOR]

The recipients of the 2018 IEEE Information Theory Society Paper Award are Mansoor I. Yousefi and Frank R. Kschischang for the three-part paper “Information Transmission Using the Nonlinear Fourier Transform, I, II, III” which appeared in the IEEE Transactions on Information Theory, vol. 60, no. 7, pp. 4312–4328 (Part I), pp. 4329–4345 (Part II), and pp. 4346–4369 (Part III), July 2014. [ABSTRACT FROM AUTHOR]