CIF: Small: Fundamental Analysis and Design of Repair-Efficient Cloud Storage Systems: a Linear Perspective

Cloud storage systems are increasingly being adopted by a wide spectrum of data intensive applications such as web search, cloud computing, distributed file sharing, and various types of data networks with high access demand, including social networks, health and medical databases, and banking system. A cloud storage system consists of several data centers and computer servers that are connected through Internet. While individual components of the system are subject to several types of failure, reliability, in the sense of data availability, and ability of regenerating failed storage nodes are two key features to design cloud storage systems. As the size of stored data and the number of users accessing the data continues to increase, designing robust, efficient, and scalable systems is a challenging and yet critically important problem. This research will develop a solid theoretical foundation for design and analysis of efficient cloud storage systems.

On the technical side, this research will focus on (1) studying the tradeoff between storage overhead and repair requirements in cloud storage systems, and (2) development of efficient coding schemes with guarantees on data recovery and failed node regeneration. While characterizing the general information-theoretic tradeoff appears to be intractable, progress can be made by limiting the problem to the class of practically relevant and low-complexity linear codes, and exploiting the duality between linear codes and multi-dimensional subspaces over finite fields. An optimization problem is formulated for this question, where an intelligent interpretation of the optimum solution provides insightful guidelines to devise code construction mechanisms. Lastly, a unified framework is proposed for code construction, to not only encompass several ad-hoc designs, but also generalize construction to all optimum operating points of the system.