Pyramid Codes

Authors:
Open Access
Publisher website
Google Scholar
Abstract
We design flexible schemes to explore the tradeoffs between storage space and access efficiency in reliable data storage systems. Aiming at this goal, two new classes of erasure-resilient codes are introduced -- Basic Pyramid Codes (BPC) and Generalized Pyramid Codes (GPC). Both schemes require slightly more storage space than conventional schemes, but significantly improve the critical performance of read during failures and unavailability. As a by-product, we establish a necessary matching condition to characterize the limit of failure recovery, that is, unless the matching condition is satisfied, a failure case is impossible to recover. In addition, we define a maximally recoverable (MR) property. For all ERC schemes holding the MR property, the matching condition becomes sufficient, that is, all failure cases satisfying the matching condition are indeed recoverable. We show that GPC is the first class of non-MDS schemes holding the MR property.
Funding Information
  • Research Grants Council, University Grants Committee, Hong Kong (411209, 411010, 411011)
  • Area of Excellence Grant (AoE/E-02/08)
  • Cisco Systems
  • Ministry of Science and Technology of the People's Republic of China (2012CB315904)
  • Microsoft
  • Open Project of Shenzhen Key Lab of Cloud Computing Technology and Application

This publication has 22 references indexed in Scilit: