36 research outputs found
Caching and Distributed Storage : Models, Limits and Designs
No full textA simple task of storing a database or transferring it to a different point via a communication channel turns far more complex as the size of the database grows large. Limited bandwidth available for transmission plays a central role in this predicament. In two broad contexts, Content Distribution Networks (CDN) and Distributed Storage Systems (DSS), the adverse effect of the growing size of the database on the transmission bandwidth can be mitigated by exploiting additional storage units. Characterizing the optimal tradeoff between the transmission bandwidth and the storage size is the central quest to numerous works in the recent literature, including this thesis.
In a DSS, individual servers fail routinely and must be replicated by downloading data from the remaining servers, a task referred to as the repair process. To render this process of repairing failed servers more straightforward and efficient, various forms of redundancy can be introduced in the system. One of the benchmarks by which the reliability of a DSS is measured is availability, which refers to the number of disjoint sets of servers that can help to repair any failed server. We study the interaction of this parameter with the amount of traffic generated during the repair process (the repair bandwidth) and the storage size. In particular, we propose a novel DSS architecture which can achieve much smaller repair bandwidth for the same availability, compared to the state of the art.
In the context of CDNs, the network can be highly congested during certain hours of the day and almost idle at other times. This variability of traffic can be reduced by utilizing local storage units that prefetch the data while the network is idle. This approach is referred to as caching. In this thesis we analyze a CDN that has access to independent data from various content providers. We characterize the best caching strategy in terms of the aggregate peak traffic under the constraint that coding across contents from different libraries is prohibited. Furthermore we prove that under certain set of conditions this restriction is without loss of optimality.LIN
Increasing Availability in Distributed Storage Systems via Clustering
No full textWe introduce the Fixed Cluster Repair System (FCRS) as a novel architecture for Distributed Storage Systems (DSS) that achieves a small repair bandwidth while guaranteeing a high availability. Specifically, we partition the set of servers in a DSS into s clusters and allow a failed server to choose any cluster other than its own as its repair group. Thereby, we guarantee an availability of s−1 . We characterize the repair bandwidth vs. storage trade-off for the FCRS under functional repair and show that the minimum repair bandwidth can be improved by an asymptotic multiplicative factor of 2/3 compared to the state of the art coding techniques that guarantee the same availability. Furthermore, we introduce cubic codes designed to minimize the repair bandwidth of the FCRS under the exact repair model. We prove an asymptotic multiplicative improvement of 0.79 in the minimum repair bandwidth compared to the existing exact repair coding techniques that achieve the same availability. We show that cubic codes are information-theoretically optimal for the FCRS with 2 and 3 complete clusters. A full version of this paper is accessible at: https://arxiv.org/pdf/1710.02653.pdfLIN
GDSP: A graphical perspective on the distributed storage systems
No full textThe classical distributed storage problem can be modeled by a k-uniform complete hyper-graph where vertices represent servers and hyper-edges represent users. Hence each hyper-edge should be able to recover the full file using only the memories of the vertices associated with it. This paper considers the generalization of this problem to arbitrary hyper-graphs and to the case of multiple files, where each user is only interested in one, a problem we will refer to as the graphical distributed storage problem (GDSP). Specifically, we make progress in the analysis of minimum-storage codes for two main subproblems of the GDSP which extend the classical model in two independent directions: the case of an arbitrary graph with multiple files, and the case of an arbitrary hyper-graph with a single file.LIN
Compute-and-Forward: Finding the Best Equation
No full textCompute-and-Forward is an emerging technique to deal with interference. It allows the receiver to decode a suitably chosen integer linear combination of the transmitted messages. The integer coefficients should be adapted to the channel fading state. Optimizing these coefficients is a Shortest Lattice Vector (SLV) problem. In general, the SLV problem is known to be prohibitively complex. In this paper, we show that the particular SLV instance resulting from the Compute-and-Forward problem can be solved in low polynomial complexity and give an explicit deterministic algorithm that is guaranteed to find the optimal solution
Effect of power randomization on saturation throughput of IEEE 802.11 WLAN
No full textIn this paper, we evaluate the saturation throughput for an IEEE 802.11 based wireless network considering capture effect at the receiver, while nodes transmit with random powers. In this respect, we consider a scenario consisting of a specific number of wireless nodes. Then, we derive the transmission as well as collision probabilities with respect to the perfect capture effect. In order to maximize the saturation throughput we set up an optimization problem and obtain how to compute optimum values for the probabilities corresponding to different power levels. By providing the numerical results, we deduce that power randomization may lead to a significant improvement in saturation throughput.IS
Comparative Evaluation of Blood Clot, Platelet-Rich Plasma, and Platelet-Rich Fibrin Scaffolds in the Success of Regenerative Endodontic Treatments: A Literature Review
No full textThe use of natural scaffolds in regenerative endodontic treatments can significantly impact treatment outcomes. Natural scaffolds such as Platelet-Rich Plasma (PRP), Platelet-Rich Fibrin (PRF), and blood clot are effective in improving clinical symptoms, resolving periapical lesions, regenerating dentin structure, closing the root apex, and increasing root length in regenerative endodontic treatments. This study aims to provide a comparative evaluation of blood clot, platelet-rich plasma (PRP), and platelet-rich fibrin (PRF) as natural scaffolds in the success of regenerative endodontic treatments
InfoCommit: Information-Theoretic Polynomial Commitment and Verification
No full textWe introduce InfoCommit, a protocol for polynomial commitment and verification. InfoCommit consists of two phases. An initial commitment phase and an evaluation phase. During the commitment phase, the verifier and the prover engage in a private two-party computation algorithm so that the verifier extracts a private verification key. In the evaluation phase, the verifier is interested in learning the evaluations of the polynomial at several input points. InfoCommit has four main features. Firstly, the verifier is able to detect, with high probability, if the prover has responded with evaluations of the same polynomial that he has initially committed to. Secondly, InfoCommit provides rigorous privacy guarantees for the prover: upon observing the initial commitment and the response provided by the prover to evaluation requests, the verifier only learns symbols about the coefficients of the polynomial. Thirdly, the verifiability guarantee is unconditional and without the need for a trusted party, while ``bounded storage is the only assumption underlying the privacy of the algorithm. In particular, both properties hold regardless of the computation power of the two parties. Lastly, InfoCommit is doubly-efficient in the sense that in the evaluation phase, the verifier runs in and the prover runs in , where is the degree of the polynomial
Multi-Library Coded Caching
No full textWe study the problem of coded caching when the server has access to several libraries and each user makes independent requests from every library. The single-library scenario has been well studied and it has been proved that coded caching can significantly improve the delivery rate compared to uncoded caching. In this work we show that when all the libraries have the same number of files, memory-sharing is optimal and the delivery rate cannot be improved via coding across files from different libraries. In this setting, the optimal memory-sharing strategy is one that divides the cache of each user proportional to the size of the files in different libraries. As for the general case, when the number of files in different libraries are arbitrary, we propose an inner-bound based on memory-sharing and an outer- bound based on concatenation of files from different libraries.LIN
Polynomially Solvable Instances of the Shortest and Closest Vector Problems With Applications to Compute-and-Forward
No full text
