Erasure coding has been recognized as a powerful method to mitigate delays due to slow or straggling nodes in distributed systems. This work shows that erasure coding of data objects can flexibly handle skews in the request rates. Coding can help boost theservice rate region, that is, increase the overall volume of data access requests that the system can handle. This paper aims to postulate the service rate region as an important consideration in the design of erasure-coded distributed systems. We highlight several open problems that can be grouped into two broad threads: 1) characterizing the service rate region of a given code and finding the optimal request allocation, and 2) designing the underlying erasure code for a given service rate region. As contributions along the first thread, we find the rate regions of maximum-distance-separable, locally repairable, and simplex codes. We show the effectiveness of hybrid codes that combine replication and erasure coding in terms of code design. We also discover fundamental connections between multi-set batch codes and the problem of maximizing the service rate region.

We study the role of coded side information in single-server Private Information Retrieval (PIR). An instance of the single-server PIR problem includes a server that stores a database of K independently and uniformly distributed messages, and a user who wants to retrieve one of these messages from the server. We consider settings in which the user initially has access to a coded side information which includes a linear combination of a subset of M messages in the database. We assume that the identities of the M messages that form the support set of the coded side information as well as the coding coefficients are initially unknown to the server. We consider two different models, depending on whether the support set of the coded side information includes the requested message or not. We also consider the following two privacy requirements: (i) the identities of both the demand and the support set of the coded side information need to be protected, or (ii) only the identity of the demand needs to be protected. For each model and for each of the privacy requirements, we consider the problem of designing a protocol for generating the user's query and the server's answer that enables the user to decode the message they need while satisfying the privacy requirement. We characterize the (scalar-linear) capacity of each setting, defined as the ratio of the number of information bits in a message to the minimum number of information bits downloaded from the server over all (scalar-linear) protocols that satisfy the privacy condition. Our converse proofs rely on new information-theoretic arguments-tailored to the setting of single-server PIR and different from the commonly-used techniques in multi-server PIR settings. We also present novel capacity-achieving scalar-linear protocols for each of the settings being considered.

Service rate is an important, recently introduced, performance metric associated with distributed coded storage systems. Among other interpretations, it measures the number of users that can be simultaneously served by the system. We introduce a geometric approach to address this problem. One of the most significant advantages of this approach over the existing ones is that it allows one to derive bounds on the service rate of a code without explicitly knowing the list of all possible recovery sets. To illustrate the power of our geometric approach, we derive upper bounds on the service rates of the first order Reed-Muller codes and the simplex codes. Then, we show how these upper bounds can be achieved. Furthermore, utilizing the proposed geometric technique, we show that given the service rate region of a code, a lower bound on the minimum distance of the code can be obtained.

We propose a novel technique for constructing a graph representation of a code through which we establish a significant connection between the service rate problem and the well-known fractional matching problem. Using this connection, we show that the service capacity of a coded storage system equals the fractional matching number in the graph representation of the code, and thus is lower bounded and upper bounded by the matching number and the vertex cover number, respectively. This is of great interest because if the graph representation of a code is bipartite, then the derived upper and lower bounds are equal, and we obtain the capacity. Leveraging this result, we characterize the service capacity of the binary simplex code whose graph representation is bipartite. Moreover, we show that the service rate problem can be viewed as a generalization of the multiset primitive batch codes problem.

A major concern in cloud/edge storage systems is serving a large number of users simultaneously. The service rate region is introduced recently as an important performance metric for coded distributed systems, which is defined as the set of all data access requests that can be simultaneously handled by the system. This paper studies the problem of designing a coded distributed storage system storing k files where a desired service rate region $\mathcal{R}$ of the system is given and the goal is 1) to determine the minimum number of storage nodes $n(\mathcal{R})$ for serving all demand vectors inside the set $\mathcal{R}$ and 2) to design the most storage-efficient redundancy scheme with the service rate region covering the set $\mathcal{R}$. Towards this goal, we propose three general lower bounds for $n(\mathcal{R})$. Also, for k = 2, we characterize $n(\mathcal{R})$, i.e., we show that the proposed lower bounds are tight, via designing a novel storage-efficient redundancy scheme with $n(\mathcal{R})$ storage nodes and service rate region covering $\mathcal{R}$.

We study the problem of single-server single-message Private Information Retrieval with Private Coded Side Information (PIR-PCSI). In this problem, there is a server that stores a database, and a user who knows a random linear combination of a random subset of messages in the database. The number of messages contributing to the user's side information is known to the server a priori, whereas the indices and the coefficients of these messages are unknown to the server a priori. The user wants to retrieve a message from the server, while protecting the identities of both the demand message and the side information messages. Depending on whether the demand is part of the coded side information or not, we consider two different models for the problem. For the model in which the demand does not contribute to the side information, we prove a lower bound on the minimum download cost for all (linear and non-linear) PIR schemes; and for the model wherein the demand is one of the messages contributing to the side information, we prove a lower bound for all scalar-linear PIR protocols. In addition, we propose novel PIR protocols that achieve these lower bounds.

In many practical settings, the user needs to retrieve information messages from a server in a periodic manner, over multiple rounds of communication. The messages are retrieved one at a time and the identity of future requests are not known to the server. In this paper, we focus on the private information retrieval protocols that ensure that the identities of all the messages retrieved from the server are protected. This scenario can occur in practical settings such as periodic content download from text and multimedia repositories. We refer to this problem of minimizing the rate of data download as online private information retrieval problem.Following the previous line of work by Kadhe et al. we assume that the user knows a subset of M messages in the database as side information. The identities of these M messages are initially unknown to the server. Focusing on scalar-linear settings, we characterize the per-round capacity, i.e., the maximum achievable download rate at each round. In particular, we show that for the setting with K messages stored at the server, the per-round capacity of the scalar-linear setting is C1= (M + 1)/K for round i = 1 and Ci= (2i -1(M + 1))/KM for round i ≥ 2, provided that K/(M + 1) is a power of 2. The key idea≥of our achievability scheme is to combine the data downloaded during the current round and the previous rounds with the original side information messages and use the resulting data as side information for the subsequent rounds.

This paper considers the problem of Quantitative Group Testing (QGT). Consider a set of N items among which K items are defective. The QGT problem is to identify (all or a sufficiently large fraction of) the defective items, where the result of a test reveals the number of defective items in the tested group. In this work, we propose a non-adaptive QGT scheme using sparse graph codes over bi-regular bipartite graphs and binary t-error-correcting BCH codes. The proposed scheme provides exact recovery with probabilistic guarantee, i.e. recovers all the defective items with high probability. In particular, we show that for the sub-linear regime where K vanishes as K, N → ∞, the proposed scheme requires at most m ≈ 1.19K log2(4.74 N/K) tests to recover all the defective items with probability approaching one as K, N → ∞. This bound can be achieved by t = 2. The testing and recovery algorithms of the proposed scheme for any t ≤ 4 have the computational complexity of O(K log2N/K) and O(K log N/K), respectively. Our simulation results also show that the proposed scheme significantly outperforms a non-adaptive semi-quantitative group testing scheme recently proposed by Abdalla et al. in terms of the required number of tests for identifying all the defective items with high probability.

This paper considers a generalized version of the coin weighing problem with a spring scale that lies at the intersection of group testing and compressed sensing problems. Given a collection of n ≥ 2 coins of total weight d (for a known integer d), where the weight of each coin is an unknown integer in the range of {0, 1, ..., k} (for a known integer k ≥ 1), the goal is to determine the weight of each coin by weighing subsets of coins in a spring scale. The problem is to devise a weighing strategy that minimizes the average number of weighings over all possible weight configurations. For d = k = 1, an adaptive bisecting weighing strategy is known to be optimal. However, even the simplest non-trivial case of the problem, i.e., d = k = 2, is still open. For this case, we propose and analyze a simple and effective adaptive weighing strategy. Our analysis shows that the proposed strategy requires about 1.365log2n-0.5 weighings on average. As n grows unbounded, the proposed strategy, when compared to an optimal strategy within the commonly-used class of nested strategies, requires about 31.75% less number of weighings on average; and in comparison with the information-theoretic lower bound, it requires at most about 8.16% extra number of weighings on average.

This paper considers the problem of single-server single-message private information retrieval with coded side information (PIR-CSI). In this problem, there is a server storing a database, and a user which knows a linear combination of a subset of messages in the database as a side information. The number of messages contributing to the side information is known to the server, but the indices and the coefficients of these messages are unknown to the server. The user wishes to download a message from the server privately, i.e., without revealing which message it is requesting, while minimizing the download cost. In this work, we consider two different settings for the PIR-CSI problem depending on the demanded message being or not being one of the messages contributing to the side information. For each setting, we prove an upper bound on the maximum download rate as a function of the size of the database and the size of the side information, and propose a protocol that achieves the rate upper-bound.

A novel mobility-aware and energy-efficient coded caching provisioning strategy, Mobee, is proposed for a Cloud Radio Access Network (C-RAN). The placement of the Maximum-Distance Separable (MDS) encoded content at the Base Stations (BSs) is optimized to minimize the total energy consumption of the network comprising the transport and the caching energy consumptions. To account for user mobility, an estimation model for content-request rates at the BSs is derived-based on the long-term content popularity and user-mobility pattern. The mobility-aware cache placement problem is then formulated as a convex optimization problem, which can be efficiently solved using standard solvers. Simulation results show that the proposed Mobee strategy significantly reduces the network energy consumption compared to traditional approaches.