This paper addresses the problem of constructing secure exact-repair regenerating codes at the MSR point for all feasible values of the parameters. The setting involves a passive eavesdropper who is allowed to observe the stored contents of, and the downloads into, an @math -subset of the @math nodes of a distributed storage system (DSS). The objective is to achieve perfect secrecy between the eavesdropped symbols and the file stored on the DSS. Previous secure code constructions (most notably that by ) tackle the problem only for the restricted case wherein the number, @math , of helper nodes aiding in the recovery of a failed node is equal to @math . This paper builds on Rawat's work, by combining Gabidulin pre-coding and an MSR construction by Ye and Barg to prove the achievability of secrecy capacity at the MSR point for all allowed values of @math .
Given a DSS that can store @math symbols when @math , we augment our file of size @math with random symbols @math , where @math is a random vector of length @math . Each random symbol in @math is drawn i.i.d. and uniformly at random from the field @math . We shall now describe the ingredients of our construction, namely the Gabidulin pre-coding procedure and the MSR construction (for all parameters @math ), by Ye and Barg @cite_7 .
@cite_7
2492240243 2606114015 2536849891 2517585112
This paper presents an explicit construction for an @math regenerating code over a field @math operating at the Minimum Storage Regeneration (MSR) point. The MSR code can be constructed to have rate @math as close to @math as desired, sub-packetization given by @math , for @math , field size no larger than @math and where all code symbols can be repaired with the same minimum data download. The construction modifies a prior construction by Sasidharan et. al. which required far larger field-size. A building block appearing in the construction is a scalar MDS code of block length @math . The code has a simple layered structure with coupling across layers, that allows both node repair and data recovery to be carried out by making multiple calls to a decoder for the scalar MDS code. While this work was carried out independently, there is considerable overlap with a prior construction by Ye and Barg. It is shown here that essentially the same architecture can be employed to construct MSR codes using vector binary MDS codes as building blocks in place of scalar MDS codes. The advantage here is that computations can now be carried out over a field of smaller size potentially even over the binary field as we demonstrate in an example. Further, we show how the construction can be extended to handle the case of @math under a mild restriction on the choice of helper nodes. Regenerating codes for distributed storage have attracted much research interest in the past decade. Such codes trade the bandwidth needed to repair a failed node with the overall amount of data stored in the network. Minimum storage regenerating (MSR) codes are an important class of optimal regenerating codes that minimize (first) the amount of data stored per node and (then) the repair bandwidth. Specifically, an @math - @math MSR code @math over @math stores a file @math consisting of @math symbols over @math among @math nodes, each storing @math symbols, in such a way that: 1) the file @math can be recovered by downloading the content of any @math of the @math nodes and 2) the content of any failed node can be reconstructed by accessing any @math of the remaining @math nodes and downloading @math symbols from each of these nodes. In practice, the file @math is typically available in uncoded form on some @math of the @math nodes, known as systematic nodes , and the defining node-repair condition above can be relaxed to requiring the optimal repair bandwidth for systematic nodes only . Such codes are called systematic–repair MSR codes . Unfortunately, finite– @math constructions of @math MSR codes are known only for certain special cases: either low rate, namely @math , or high repair connectivity, namely @math . Our main result in this paper is a finite– @math construction of systematic-repair @math MSR codes for all possible values of parameters @math . We also introduce a generalized construction for @math MSR codes to achieve the optimal repair bandwidth for all values of @math simultaneously. We study the recovery of sparse vectors from subsampled random convolutions via @math -minimization. We consider the setup in which both the subsampling locations as well as the generating vector are chosen at random. For a subgaussian generator with independent entries, we improve previously known estimates: if the sparsity @math is small enough, i.e., @math , we show that @math measurements are sufficient to recover @math -sparse vectors in dimension @math with high probability, matching the well-known condition for recovery from standard Gaussian measurements. If @math is larger, then essentially @math measurements are sufficient, again improving over previous estimates. Our results are shown via the so-called robust null space property which is weaker than the standard restricted isometry property. Our method of proof involves a novel combination of small ball estimates with chaining techniques which should be of independent interest. We study a noiseless broadcast link serving @math users whose requests arise from a library of @math files. Every user is equipped with a cache of size @math files each. It has been shown that by splitting all the files into packets and placing individual packets in a random independent manner across all the caches prior to any transmission, at most @math file transmissions are required for any set of demands from the library. The achievable delivery scheme involves linearly combining packets of different files following a greedy clique cover solution to the underlying index coding problem. This remarkable multiplicative gain of random placement and coded delivery has been established in the asymptotic regime when the number of packets per file @math scales to infinity. The asymptotic coding gain obtained is roughly @math . In this paper, we initiate the finite-length analysis of random caching schemes when the number of packets @math is a function of the system parameters @math , and @math . Specifically, we show that the existing random placement and clique cover delivery schemes that achieve optimality in the asymptotic regime can have at most a multiplicative gain of 2 even if the number of packets is exponential in the asymptotic gain @math . Furthermore, for any clique cover-based coded delivery and a large class of random placement schemes that include the existing ones, we show that the number of packets required to get a multiplicative gain of @math is at least @math . We design a new random placement and an efficient clique cover-based delivery scheme that achieves this lower bound approximately. We also provide tight concentration results that show that the average (over the random placement involved) number of transmissions concentrates very well requiring only a polynomial number of packets in the rest of the system parameters.