Technical Report MSC-2018-04

Title: Constructions of PIR and Batch Codes for Distributed Storage
Authors: Hilal Asi
Supervisors: Eitan Yaakobi
PDFCurrently accessibly only within the Technion network
Abstract: Distributed and cloud storage systems today are required to tolerate the failure or unavailability of some of the nodes in the system. The simplest and most commonly method to accomplish this task is by replication, whereby every node is replicated several times, usually three. This solution has clear advantages due to its simplicity, fast recovery, and efficient availability. However, it entails a large storage overhead which becomes costly in large storage systems. Availability in particular plays an important role in supporting high throughput of the system. Consider the case in which a large number of files are stored in a distributed storage system and user requests of the files are received. If each file has one copy or can be recovered only once, and several users request this file, then these requests will have to be served sequentially, which will significantly slow down the system’s response time. In this work we study two families of codes with availability for distributed storage. The first family of codes, called private information retrieval (PIR) codes, requires that every information symbol has some k mutually disjoint recovering sets. The second family of codes, which is a generalization of the first one, was first proposed in the last decade by Ishai et al. under the framework of batch codes. These codes were originally motivated by different applications such as load-balancing in storage and cryptographic protocols. Under this setting, it is required that every multiset request of k symbols can be recovered by k mutually disjoint recovering sets. Note that every batch code is in particular a PIR code with the same parameters.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the MSC technical reports of 2018
To the main CS technical reports page

Computer science department, Technion