In this work, a distributed server system composed of multiple servers that holds some coded files and multiple users that are interested in retrieving the linear functions of the files is investigated, where the servers are robust, blind and adversarial in the sense that any J servers can together recover all files, while any I colluding servers cannot obtain any information about the files, and at most A servers maliciously provides erroneous information. In addition, the file library must be secure from a wiretapper who obtains all the signals, and the demands of any subset of users must kept private from the other users and servers, even if they collude. A coding scheme is proposed by incorporating the ideas of Shamir’s secret sharing and key superposition into the framework of Placement Delivery Array (PDA), originally proposed to characterize the single-server coded caching system without any security or privacy constraints. It is shown that PDAs associated to Maddah-Ali and Niesen’s coded caching scheme results in an achievable memory-storage-communication region, such that the storage size and communication load were optimal to within a multiplicative gap, except for the small memory regime when the number of files was smaller than the number of users.

Coded distributed computing can alleviate the communication load by leveraging the redundant storage and computation resources with coding techniques in distributed computing. In this paper, we study a MapReduce-type distributed computing framework over star topological network, where all the workers exchange information through a common access point. The optimal tradeoff among the normalized number of stored files (storage load), computed intermediate values (computation load), and transmitted bits in the uplink and downlink (communication loads) is characterized. A coded computing scheme is proposed to achieve the Pareto-optimal tradeoff surface, in which the access point only needs to perform simple chain coding between the signals it receives, and information- theoretical bound matching the surface is also provided.

This work investigates a system where each user aims to retrieve a scalar linear function of the files of a library, which are Maximum Distance Separable coded and stored at multiple distributed servers. The system needs to guaranteerobust decodingin the sense that each user must decode its demanded function with signals received from any subset of servers whose cardinality exceeds a threshold. In addition, (a) the content of the library must be kept secure from a wiretapper who obtains all the signals from the servers; (b) any subset of users together can not obtain any information about the demands of the remaining users; and (c) the users’ demands must be kept private against all the servers even if they collude. Achievable schemes are derived by modifying existing Placement Delivery Array (PDA) constructions, originally proposed for single-server single-file retrieval coded caching systems without any privacy or security or robustness constraints. It is shown that the PDAs describing the original Maddah-Ali and Niesen’s coded caching scheme result in a load-memory tradeoff that is optimal to within a constant multiplicative gap, except for the small memory regime when the number of file is smaller than the number of users. As by-products, improved order optimality results are derived for three less restrictive systems in all parameter regimes.

The problem of Multi-user Blind$X$-secure$T$-colluding Symmetric Private Information Retrieval from Maximum Distance Separable (MDS) coded storage system with$B$Byzantine and$U$unresponsive servers (U-B-MDS-MB-XTSPIR) is studied in this paper. Specifically, a database consisting of multiple files, each labeled by$M$indices, is stored at the distributed system with$N$servers according to$(N,K+X)$MDS codes over$\mathbb {F}_{q}$such that any group of up to$X$colluding servers learn nothing about the data files. There are$M$users, in which each user$m,m=1,\ldots,M$privately selects an index$\theta _{m}$and wishes to jointly retrieve the file specified by the$M$users’ indices$(\theta _{1},\ldots,\theta _{M})$from the storage system, while keeping its index$\theta _{m}$private from any$T_{m}$colluding servers, where there exists$B$Byzantine servers that can send arbitrary responses maliciously to confuse the users retrieving the desired file and$U$unresponsive servers that will not respond any message at all. In addition, each user must not learn information about the other users’ indices and the database more than the desired file. An U-B-MDS-MB-XTSPIR scheme is constructed based on Lagrange encoding. The scheme achieves a retrieval rate of$1-\frac {K+X+T_{1}+\ldots +T_{M}+2B-1}{N-U}$with secrecy rate$\frac {K+X+T_{1}+\ldots +T_{M}-1}{ N-(K+X+T_{1}+\ldots +T_{M}+2B+U-1)}$on the finite field of size$q\geq N+\max \{K, N-(K+X+T_{1}+\ldots +T_{M}+2B+U-1)\}$for any number of files.

Distributed computing has become one of the most important frameworks in dealing with large computation tasks. In this paper, we propose a systematic construction of coded computing schemes for MapReduce-type distributed systems. The construction builds upon placement delivery arrays (PDA), originally proposed by Yanet al.for coded caching schemes. The main contributions of our work are three-fold. First, we identify a class of PDAs, calledComp-PDAs, and show how to obtain a coded computing scheme from any Comp-PDA. We also characterize the normalized number of stored files (storage load), computed intermediate values (computation load), and communicated bits (communication load), of the obtained schemes in terms of the Comp-PDA parameters. Then, we show that the performance achieved by Comp-PDAs describing Maddah-Ali and Niesen’s coded caching schemes matches a new information-theoretic converse, thus establishing the fundamental region of all achievable performance triples. In particular, we characterizeallthe Comp-PDAs achieving the pareto-optimal storage, computation, and communication (SCC) loads of the fundamental region. Finally, we investigate the file complexity of the proposed schemes, i.e., the smallest number of files required for implementation. In particular, we describe Comp-PDAs that achieve pareto-optimal SCC triples with significantly lower file complexity than the originally proposed Comp-PDAs.

The problem of$X$-secure$T$-colluding symmetric Private Polynomial Computation (PPC) from coded storage system with$B$Byzantine and$U$unresponsive servers is studied in this paper. Specifically, a dataset consisting of$M$files is stored across$N$distributed servers according to$(N,K+X)$Maximum Distance Separable (MDS) codes such that any group of up to$X$colluding servers can not learn anything about the data files. A user wishes to privately evaluate one out of a set of candidate polynomial functions over the$M$files from the system, while guaranteeing that any$T$colluding servers can not learn anything about the identity of the desired function and the user can not learn anything about the$M$data files more than the desired polynomial function evaluations, in the presence of$B$Byzantine servers that can send arbitrary responses maliciously to confuse the user and$U$unresponsive servers that will not respond any information at all. A novel symmetric PPC scheme using Lagrange encoding is proposed. This scheme achieves a PPC rate of$1-\frac {G(K+X-1)+T+2B}{N-U}$with secrecy rate$\frac {G(K+X-1)+T}{N-(G(K+X-1)+T+2B+U)}$and finite field size$N+\max \{K,N-(G(K+X-1)+T+2B+U)\}$, where$G$is the maximum degree over all the candidate polynomial functions. Moreover, to further measure the efficiency of PPC schemes, upload cost, query complexity, server computation complexity and decoding complexity required to implement the scheme are analyzed. Remarkably, the PPC setup studied in this paper generalizes all the previous MDS coded PPC setups and the degraded schemes strictly outperform the best known schemes in terms of (asymptotical) PPC rate, which is the main concern of the PPC schemes.

This paper focuses on mitigating the impact of stragglers in distributed learning system. Unlike the existing results designated for a fixed number of stragglers, we develop a new scheme calledAdaptive Gradient Coding (AGC)with flexible communication cost for varying number of stragglers. Our scheme gives an optimal tradeoff between computation load, straggler tolerance and communication cost by allowing workers to send multiple signals sequentially to the master. In particular, it can minimize the communication cost according to the unknown real-time number of stragglers in practical environments. In addition, we present aGroup AGC (G-AGC)by combining the group idea with AGC to resist more stragglers in some situations. The numerical and simulation results demonstrate that our adaptive schemes can achieve the smallest average running time.

This paper investigates the ultimate performance limits of distributed multi-server systems with cache-aided users, where the users aim to retrieve a linear function of the files of a library that are replicated at multiple non-colluding servers. In addition to correct decoding, the following conditions are imposed: (a) the content of the library must be kept secure from a wiretapper who obtains all the signals sent by the servers; (b) any subset of users together can not obtain any information about the demands of the remaining users; and (c) the users’ demands must be kept private against any individual server. A Distributed Key Superposition (DKS) scheme is proposed, which uses the idea of superposition of security and privacy keys to guarantee conditions (a) and (b) simultaneously, as in the single server setup. Condition (c) is guaranteed by the fact that each server is responsible for delivering a fraction of the requested linear function, and insuring that the privacy keys used by a server are generated and pushed to the user caches by another server. Interestingly, the achievable load-memory tradeoff with the additional constraint (c) is the same as the single server case if there are at least two servers.

Matrix factorization is an important representation learning algorithm, e.g., recommender systems, where a large matrix can be factorized into the product of two low dimensional matrices termed as latent representations. This paper investigates the problem of matrix factorization in distributed computing systems with stragglers, those computing nodes that are slow to return computation results. A computation procedure, called coded Alternative Least Square (ALS), is proposed for mitigating the effect of stragglers in such systems. The coded ALS algorithm iteratively computes two low dimensional latent matrices by solving various linear equations, with the Entangled Polynomial Code (EPC) as a building block. We theoretically characterize the maximum number of stragglers that the algorithm can tolerate (or the recovery threshold) in relation to the redundancy of coding (or the code rate). In addition, we theoretically show the computation complexity for the coded ALS algorithm and conduct numerical experiments to validate our design.

This paper investigates the ultimate performance limits of Linear Function Retrieval (LFR) by cache-aided users from distributed coded servers. Each user aims to retrieve a linear function of the files of a library, which are Maximum Distance Separable (MDS) coded and stored at multiple servers. The system needs to guarantee robust decoding in the sense that each user must decode its demanded function with signals from any subset of servers whose cardinality exceeds a threshold. In addition, the following conditions must be met: (a) the content of the library must be kept secure from a wiretapper who obtains all the signals sent by the servers; (b) any subset of users together can not obtain any information about the demands of the remaining users; and (c) the users' demands must be kept private against all the servers even if they collude. A scheme that uses the superposition of security and privacy keys is proposed to meet all those conditions. The achieved load-memory tradeoff is the same as that achieved in single-server case scaled by the inverse of the MDS code rate used to encode the files, and the same optimality guarantees as in single-server setup are obtained.

This paper investigates the problem of Secure Multi-party Batch Matrix Multiplication (SMBMM), where a user aims to compute the pairwise products$\mathbf {A}\divideontimes \mathbf {B}\triangleq (\mathbf {A}^{(1)}\mathbf {B}^{(1)},\ldots,\mathbf {A}^{(M)}\mathbf {B}^{(M)})$of two batch of massive matrices$\mathbf {A}$and$\mathbf {B}$that are generated from two sources, through$N$honest but curious servers which share some common randomness. The matrices$\mathbf {A}$(resp.$\mathbf {B}$) must be kept secure from any subset of up to$X_{\mathbf {A}}$(resp.$X_{\mathbf {B}}$) servers even if they collude, and the user must not obtain any information about$(\mathbf {A},\mathbf {B})$beyond the products$\mathbf {A}\divideontimes \mathbf {B}$. A novel computation strategy for single secure matrix multiplication problem (i.e., the case$M=1$) is first proposed, and then is generalized to the strategy for SMBMM by means of cross subspace alignment. The SMBMM strategy focuses on the tradeoff between recovery threshold (the number of successful computing servers that the user needs to wait for), system cost (upload cost, the amount of common randomness, and download cost) and system complexity (encoding, computing, and decoding complexities). Notably, compared with the known result by Chenet al., the strategy for the degraded case$X= X_{\mathbf {A}}=X_{\mathbf {B}}$achieves better recovery threshold, amount of common randomness, download cost and decoding complexity when$X$is less than some parameter threshold, while the performance with respect to other measures remain identical.

This work investigates the problem of cache-aided content Secure and demand Private Linear Function Retrieval (SP-LFR), where three constraints are imposed on the system: (a) each user is interested in retrieving an arbitrary linear combination of the files in the server’s library; (b) the content of the library must be kept secure from a wiretapper who obtains the signal sent by the server; and (c) no subset of colluding users together can obtain information about the demands of the remaining users. A procedure is proposed to derive an SP-LFR scheme from a given Placement Delivery Array (PDA), which is known to give coded caching schemes with low subpacketization for systems with neither security nor privacy constraints. This procedure uses the superposition of security keys and privacy keys, in both the cache placement and transmitted signal, to guarantee content security and demand privacy, respectively. In particular, among all PDA-based SP-LFR schemes, the memory-load pairs achieved by the PDA describing the Maddah-Ali and Niesen’s scheme are Pareto optimal and have the lowest subpacketization. Moreover, the achieved load-memory tradeoff is optimal to within a constant multiplicative gap, except for the small memory regime (i.e., when the cache size is between 1 and 2) and the number of files is smaller than the number of users. Remarkably, the memory-load tradeoff does not worsen compared to the best known schemes that guarantee either only content security in all regimes or only demand privacy in the regime mentioned above.

This paper investigates reducing sub-packetization of capacity-achieving schemes for uncoded Storage Constrained Private Information Retrieval (SC-PIR) systems. In the SC-PIR system, a user aims to download one out of K files from N servers while revealing nothing about the identity of the requested file to any individual server, in which the K files are stored at the N servers in an uncoded form and each server can store up to μK equivalent files, where μ is the normalized storage capacity of each server. We first prove that there exists a capacity-achieving SC-PIR scheme for a given storage design if and only if all the packets are stored exactly at M\triangleq μN servers for μ such that M=μN ∈ {2,3,...,N}. Then, the optimal sub-packetization for capacity-achieving linear SC-PIR schemes is characterized as the solution to an optimization problem, which is typically hard to solve since it involves non-continuous indicator functions. Moreover, a new notion of array called Storage Design Array (SDA) is introduced for the SC-PIR system. With any given SDA, an associated capacity-achieving SC-PIR scheme is constructed. Next, the SC-PIR schemes that have equal-size packets are investigated. Furthermore, the optimal equal-size sub-packetization among all capacity-achieving linear SC-PIR schemes characterized by Woolsey et al. is proved to be \frac N(M-1)gcd(N,M), which is achieved by a construction of SDA. Finally, by allowing unequal size of packets, a greedy SDA construction is proposed, where the sub-packetization of the associated SC-PIR scheme is upper bounded by \frac N(M-1)gcd(N,M). Among all capacity-achieving linear SC-PIR schemes, the sub-packetization is optimal when min{M,N-M}|N or M=N, and within a multiplicative gap \frac min{M,N-M}gcd(N,M) of the optimal one in general. In particular, for the special case N=d·M±1 where the positive integer d ≥ 2, we propose another SDA construction to obtain lower sub-packetization.

A coded caching scheme, referred to as key superposition, is proposed in the cache-aided content Secure and demand Private Linear Function Retrieval (SP-LFR) setup, where the following conditions are imposed: (a) each user is interested in retrieving an arbitrary linear combination of the files in the server’s library; (b) the content of the library must be kept secure from a wiretapper who obtains the signal sent by the server; and (c) any subset of users together can not obtain any information about the demands of the remaining users. The scheme uses the superposition of security keys and privacy keys in both the placement and delivery phases to guarantee content security and demand privacy, respectively. The achieved load-memory tradeoff is optimal to within a constant multiplicative gap, except for the small memory regime when there are less file than users. The memory-load tradeoff does not increase compared to the best known schemes that only guarantee content security in all regimes or only demand privacy in some regime.

In coded caching system, we prefer to design a scheme with the rate R and the packet number F of each file split as small as possible since the efficiency of transmission in the peak traffic times increases with the decreasing of R and the realizing complexity increases with the increasing of F. Up to now, almost all of the previously known schemes can be realized by the combinatorial structure which is called placement delivery array (PDA). In this paper, we also study the schemes by means of PDAs. We first show that given the minimum rate, the scheme proposed by Maddah-Ali and Niesen (MN scheme) has the minimum packet number which is too large in practice. From the view point of combinatorial design, two variant MN schemes, which can significantly reduce the packet number by increasing some rate, are obtained. Especially one of these schemes has better performance than the scheme generated by the well known grouping method.

Placement delivery arrays for distributed computing (Comp-PDAs) have recently been proposed as a framework to construct universal computing schemes for MapReduce-like systems. In this work, we extend this concept to systems with straggling nodes, i.e., to systems where a subset of the nodes cannot accomplish the assigned map computations in due time. Unlike most previous works that focused on computing linear functions, our results are universal and apply for arbitrary map and reduce functions. Our contributions are as follows. Firstly, we show how to construct a universal coded computing scheme for MapReduce-like systems with straggling nodes from any given Comp-PDA. We also characterize the storage and communication loads of the resulting scheme in terms of the Comp-PDA parameters. Then, we prove an information-theoretic converse bound on the storage-communication (SC) tradeoff achieved by universal computing schemes with straggling nodes. We show that the information-theoretic bound matches the performance achieved by the coded computing schemes with straggling nodes corresponding to the Maddah-Ali and Niesen (MAN) PDAs, i.e., to the Comp-PDAs describing Maddah-Ali and Niesen's coded caching scheme. Interestingly, the MAN-PDAs are optimal for any number of straggling nodes. This implies that the map phase of optimal coded computing schemes does not need to be adapted to the number of stragglers in the system. We show that the points that lie exactly on the fundamental SC tradeoff cannot be achieved with Comp-PDAs that require smaller number of files than the MAN-PDAs. This is however possible for some of the points that lie close to the SC tradeoff. For these latter points, the decrease in the requested number of files can be exponential in the number of nodes of the system. We also model the total execution time, and numerically show that the active set size should be chosen to balance the duration of the map phase and the durations of the shuffle and reduce phases.

In a distributed storage system, private information retrieval (PIR) guarantees that a user retrieves one file from the system without revealing any information about the identity of its interested file to any individual server. In this paper, we investigate an (N, K, M) coded server model of PIR, where each of M files is distributed to N servers in the form of (N, K) maximum distance separable (MDS) code for some N > K and M > 1. As a result, we propose a new capacity-achieving (N, K, M) coded linear PIR scheme such that it can be implemented with file length (K(N-K)/(gcd(N,K)), which is much smaller than the previous best result K(N/(gcd(N,K)))M-1. Notably, among all the capacity-achieving coded linear PIR schemes, we show that the file length is optimal if M > ⌊K/(gcd(N,K)) - K/(N-K)⌋ + 1 or min(K, N - K)|N, and within a multiplicative gap (min(K,N-K))/(gcd(N,K) ) of a lower bound on the minimum file length otherwise.

The optimal storage-computation tradeoff is characterized for a MapReduce-like distributed computing system with straggling nodes, where only a part of the nodes can be utilized to compute the desired output functions. The result holds for arbitrary output functions and thus generalizes previous results that restricted to linear functions. Specifically, in this work, we propose a new information-theoretical converse and a new matching coded computing scheme, that we call coded computing for straggling systems (CCS).

Coded caching scheme recently has become quite popular in the wireless network, since the maximum transmission amount R reduces effectively during the peak-traffic times. To realize a coded caching scheme, each file must be divided into F packets, which usually increases the computation complexity of a coded caching scheme. So we prefer to design a scheme with R and F as small as possible in practice. However, there exists a tradeoff between R and F. In this paper, we generalize the schemes constructed by Shangguan et al. (IEEE TRANSACTIONS ON INFORMATION THEORY, 64, 5755-5766, 2018) and Yan et al. (IEEE TRANSACTIONS ON INFORMATION THEORY 63, 5821-5833, 2017), respectively. These two classes of schemes have a wider range of application due to the more flexible memory size than the original ones. By comparing with the previous known deterministic schemes, our new schemes have advantages on R or F.

Ji et al. (IEEE TRANSACTIONS ON INFORMATION THEORY, 62(2): 849-869, 2016) first studied coded caching in device-to-device (D2D) networks, and proposed a D2D coded caching scheme, which is referred to as the JCM scheme. In practice, we prefer to design a scheme with its two important targets, i.e., the rate (the maximal total amount of transmission) and packet number F, as small as possible. In this paper, we first propose a simple array called D2D placement delivery array (DPDA) to characterize the placement phase and the delivery phase in D2D networks. Consequently, some D2D coded caching schemes can be realized by an appropriate DPDA. Second, a lower bound on the rate of a DPDA is derived. And, we show that the JCM scheme achieves our lower bound. However, it is well known that its packet number F increases exponentially with the number of users K. So, we propose two classes of new schemes by constructing DPDAs. One reduces the packet number exponentially with K compared with the JCM scheme while keeping the rate near to our lower bound. The other further reduces F to increasing sub-exponentially with K.

A major practical limitation of the Maddah-Ali-Niesen coded caching techniques is their high subpacketization level. For the simple network with a single server and multiple users, Yan et al. proposed an alternative scheme with the so-called placement delivery arrays (PDA). Such a scheme requires slightly higher transmission rates but significantly reduces the subpack-etization level. In this paper, we extend the PDA framework and propose three low-subpacketization schemes for combination networks, i.e., networks with a single server, multiple relays, and multiple cache-aided users that are connected to subsets of relays. One of the schemes achieves the cutset lower bound on the link rate when the cache memories are sufficiently large. Our other two schemes apply only to resolvable combination networks. For these network and for a wide range of cache sizes, the new schemes perform closely to the coded caching schemes that directly apply Maddah-Ali-Niesen scheme while having significantly reduced subpacketization levels.

Recently, placement delivery array (PDA) was formulated to describe the placement and delivery phases with a single array for centralized coded caching scheme in an error-free shared link. In this paper, we explore PDA characterizations for two other models: device-to-device (D2D) network and distributed computing system. The inherent connections between these systems and the shared link caching system are displayed through PDA, which allows us to transform the PDA based schemes originally designated for shared link to those networks. As a result, combining with existing constructions, we can obtain schemes requiring low subpacketization level for D2D network or smaller number of files for distributed computing system.

We consider a MapReduce-like distributed computing system. We derive a lower bound on the communication cost for any given storage and computation costs. This lower bound matches the achievable bound we proposed recently. As a result, we completely characterize the optimal tradeoff between the storage, the computation, and the communication. Our result generalizes the previous one by Li et at. to also account for the number of computed intermediate values.

Being able to provide a relatively easy and inexpensive way to collect data, portable readers have gained increasing popularity in wide-ranging RFID applications. In order to maximize the reader’s battery life, efficient tag identification protocols are of paramount importance in large-scale passive radio frequency identification (RFID) systems. This paper proposes a time- and energy-aware protocol based on$M$-ary collision tree (MCT) for efficient RFID tag identification. Thanks to Manchester encoding, the proposed MCT protocol recursively divides colliding tags into$M$subsets with at least two nonempty ones according to the information of$\log _2 M$colliding bits. Through the new MCT recognition process, MCT can effectively identify all the tags within its reading range. Theoretic analysis demonstrates that it takes the proposed MCT protocol fewer numbers of collision slots and message bits to identify all the tags, which reduces not only the identification time but also the energy cost. Simulation results are also presented to show that compared with other benchmark works, the proposed MCT protocol is able to reduce the average identification time and energy cost by at least 16.12% and 15.73%, respectively.

Caching is a promising solution to satisfy the ever-increasing demands for the multi-media traffics. In caching networks, coded caching is a recently proposed technique that achieves significant performance gains over the uncoded caching schemes. However, to implement the coded caching schemes, each file has to be split into F packets, which usually increases exponentially with the number of users K. Thus, designing caching schemes that decrease the order of F is meaningful for practical implementations. In this paper, by reviewing the Ali-Niesen caching scheme, the placement delivery array (PDA) design problem is first formulated to characterize the placement issue and the delivery issue with a single array. Moreover, we show that, through designing appropriate PDA, new centralized coded caching schemes can be discovered. Second, it is shown that the Ali-Niesen scheme corresponds to a special class of PDA, which realizes the best coding gain with the least F. Third, we present a new construction of PDA for the centralized coded caching system, wherein the cache size M at each user (identical cache size is assumed at all users) and the number of files N satisfies M/N = 1/q or (q - 1)/q (q is an integer, such that q ≥ 2). The new construction can decrease the required F from the order O(eK·((M/N) ln(N/M)+(1-(M/N)) ln (N/(N-M))) of Ali-Niesen scheme to O(eK·(M/N) ln(N/M)) or O(eK·(1-(M/N)) ln(N/(N-M))), respectively, while the coding gain loss is only 1.