This paper provides a link between matroid theory and locally repairable codes (LRCs) that are either linear or more generally almost affine. Using this link, new results on both LRCs and matroid ...theory are derived. The parameters (n, k, d, r, δ) of LRCs are generalized to matroids, and the matroid analog of the generalized singleton bound by Gopalan et al. for linear LRCs is given for matroids. It is shown that the given bound is not tight for certain classes of parameters, implying a nonexistence result for the corresponding locally repairable almost affine codes that are coined perfect in this paper. Constructions of classes of matroids with a large span of the parameters (n, k, d, r, δ) and the corresponding local repair sets are given. Using these matroid constructions, new LRCs are constructed with prescribed parameters. The existence results on linear LRCs and the nonexistence results on almost affine LRCs given in this paper strengthen the nonexistence and existence results on perfect linear LRCs given by Song et al.
In quantum private information retrieval (QPIR), a user retrieves a classical file from multiple servers by downloading quantum systems without revealing the identity of the file. The QPIR capacity ...is the maximal achievable ratio of the retrieved file size to the total download size. In this paper, the capacity of QPIR from MDS-coded and colluding servers is studied for the first time. Two general classes of QPIR, called stabilizer QPIR and dimension-squared QPIR induced from classical strongly linear PIR are defined, and the related QPIR capacities are derived. For the non-colluding case, the general QPIR capacity is derived when the number of files goes to infinity. A general statement on the converse bound for QPIR with coded and colluding servers is derived showing that the capacities of stabilizer QPIR and dimension-squared QPIR induced from any class of PIR are upper bounded by twice the classical capacity of the respective PIR class. The proposed capacity-achieving scheme combines the star-product scheme by Freij-Hollanti et al. and the stabilizer QPIR scheme by Song et al. by employing (weakly) self-dual Reed-Solomon codes.
In this paper, locally repairable codes with all-symbol locality are studied. Methods to modify already existing codes are presented. It is also shown that, with high probability, a random matrix ...with a few extra columns guaranteeing the locality property is a generator matrix for a locally repairable code with a good minimum distance. The proof of the result provides a constructive method to find locally repairable codes. Finally, constructions of three infinite classes of optimal vector-linear locally repairable codes over a small alphabet independent of the code size are given.
This paper presents a new alphabet-dependent bound for codes with hierarchical locality. Then, the complete list of possible localities is derived for a class of codes obtained by deleting specific ...columns from a Simplex code. This list is used to show that these codes are optimal codes with hierarchical locality.
In this paper, a general framework for linear secure distributed matrix multiplication (SDMM) is introduced. The model allows for a neat treatment of straggling and Byzantine servers via a star ...product interpretation as well as simplified security proofs. Known properties of star products also immediately yield a lower bound for the recovery threshold as well as an upper bound for the number of colluding workers the system can tolerate. Another bound on the recovery threshold is given by the decodability condition, which generalizes a bound for GASP codes. The framework produces many of the known SDMM schemes as special cases, thereby providing unification for the previous literature on the topic. Furthermore, error behavior specific to SDMM is discussed and interleaved codes are proposed as a suitable means for efficient error correction in the proposed model. Analysis of the error correction capability under natural assumptions about the error distribution is also provided, largely based on well-known results on interleaved codes. Error detection and other error distributions are also discussed.
In this paper, we study the problem of private and secure distributed matrix multiplication (PSDMM) , where a user having a private matrix <inline-formula> <tex-math notation="LaTeX">A ...</tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">N </tex-math></inline-formula> non-colluding servers sharing a library of <inline-formula> <tex-math notation="LaTeX">L </tex-math></inline-formula> (<inline-formula> <tex-math notation="LaTeX">L>1 </tex-math></inline-formula>) matrices <inline-formula> <tex-math notation="LaTeX">B^{(0)}, B^{(1)},\ldots,B^{(L-1)} </tex-math></inline-formula>, for which the user wishes to compute <inline-formula> <tex-math notation="LaTeX">AB^{(\theta)} </tex-math></inline-formula> for some <inline-formula> <tex-math notation="LaTeX">\theta \in 0, L </tex-math></inline-formula>) without revealing any information of the matrix <inline-formula> <tex-math notation="LaTeX">A </tex-math></inline-formula> to the servers, and keeping the index <inline-formula> <tex-math notation="LaTeX">\theta </tex-math></inline-formula> private to the servers. Previous work is limited to the case that the shared library ( i.e., the matrices <inline-formula> <tex-math notation="LaTeX">B^{(0)}, B^{(1)},\ldots,B^{(L-1)} </tex-math></inline-formula>) is stored across the servers in a replicated form and schemes are very scarce in the literature, there is still much room for improvement. In this paper, we propose two PSDMM schemes, where one is limited to the case that the shared library is stored across the servers in a replicated form but has a better performance than state-of-the-art schemes in that it can achieve a smaller recovery threshold and download cost. The other one focuses on the case that the shared library is stored across the servers in an MDS-coded form, which requires less storage in the servers. The second PSDMM code does not subsume the first one even if the underlying MDS code is degraded to a repetition code as they are totally two different schemes.
In the classical private information retrieval (PIR) setup, a user wants to retrieve a file from a database or a distributed storage system (DSS) without revealing the file identity to the servers ...holding the data. In the quantum PIR (QPIR) setting, a user privately retrieves a classical file by receiving quantum information from the servers. The QPIR problem has been treated by Song et al. in the case of replicated servers, both without collusion and with all but one servers colluding. In this paper, the QPIR setting is extended to account for maximum distance separable (MDS) coded servers. The proposed protocol works for any <inline-formula> <tex-math notation="LaTeX">n,k </tex-math></inline-formula>-MDS code and <inline-formula> <tex-math notation="LaTeX">t </tex-math></inline-formula>-collusion with <inline-formula> <tex-math notation="LaTeX">t=n-k </tex-math></inline-formula>. Similarly to the previous cases, the rates achieved are better than those known or conjectured in the classical counterparts. Further, it is demonstrated how the protocol can adapted to achieve significantly higher retrieval rates from DSSs encoded with a locally repairable code (LRC) with disjoint repair groups, each of which is an MDS code.
In forthcoming years, the Internet of Things (IoT) will connect billions of smart devices generating and uploading a deluge of data to the cloud. If successfully extracted, the knowledge buried in ...the data can significantly improve the quality of life and foster economic growth. However, a critical bottleneck for realizing the efficient IoT is the pressure it puts on the existing communication infrastructures, requiring transfer of enormous data volumes. Aiming at addressing this problem, we propose a novel architecture dubbed Condense which integrates the IoT-communication infrastructure into the data analysis. This is achieved via the generic concept of network function computation. Instead of merely transferring data from the IoT sources to the cloud, the communication infrastructure should actively participate in the data analysis by carefully designed en-route processing. We define the Condense architecture, its basic layers, and the interactions among its constituent modules. Furthermore, from the implementation side, we describe how Condense can be integrated into the Third Generation Partnership Project (3GPP) machine type communications (MTCs) architecture, as well as the prospects of making it a practically viable technology in a short time frame, relying on network function virtualization and software-defined networking. Finally, from the theoretical side, we survey the relevant literature on computing atomic functions in both analog and digital domains, as well as on function decomposition over networks, highlighting challenges, insights, and future directions for exploiting these techniques within practical 3GPP MTC architecture.
Special issue on network coding Monteiro, Francisco A.; Burr, Alister; Chatzigeorgiou, Ioannis ...
EURASIP Journal on Advances in Signal Processing,
04/2017, Volume:
2017, Issue:
1
Journal Article
Peer reviewed
Open access
Future networks are expected to depart from traditional routing schemes in order to embrace network coding (NC)-based schemes. These have created a lot of interest both in academia and industry in ...recent years. Under the NC paradigm, symbols are transported through the network by combining several information streams originating from the same or different sources.
This special issue contains thirteen papers, some dealing with design aspects of NC and related concepts (e.g., fountain codes) and some showcasing the application of NC to new services and technologies, such as data multi-view streaming of video or underwater sensor networks. One can find papers that show how NC turns data transmission more robust to packet losses, faster to decode, and more resilient to network changes, such as dynamic topologies and different user options, and how NC can improve the overall throughput. This issue also includes papers showing that NC principles can be used at different layers of the networks (including the physical layer) and how the same fundamental principles can lead to new distributed storage systems. Some of the papers in this issue have a theoretical nature, including code design, while others describe hardware testbeds and prototypes.
The problem of private information retrieval (PIR) from coded storage systems with colluding, Byzantine, and unresponsive servers is considered. An explicit scheme using an <inline-formula> <tex-math ...notation="LaTeX">n,k </tex-math></inline-formula> Reed-Solomon storage code is designed, protecting against <inline-formula> <tex-math notation="LaTeX">t </tex-math></inline-formula>-collusion, and handling up to <inline-formula> <tex-math notation="LaTeX">b </tex-math></inline-formula> Byzantine and <inline-formula> <tex-math notation="LaTeX">r </tex-math></inline-formula> unresponsive servers, when <inline-formula> <tex-math notation="LaTeX">n>k+t+2b+r-1 </tex-math></inline-formula>. This scheme achieves a PIR rate of <inline-formula> <tex-math notation="LaTeX">(({n-r-(k+2b+t-1)})/{n-r}) </tex-math></inline-formula>. In the case where the capacity is known, namely, when <inline-formula> <tex-math notation="LaTeX">k=1 </tex-math></inline-formula>, it is asymptotically capacity achieving as the number of files grows. Finally, the scheme is adapted to symmetric PIR.
PDF
