Most large-scale storage systems employ erasure coding to provide resilience against disk failures. Recent work has shown that tuning this redundancy to changes in disk failure rates leads to substantial storage savings. This process requires code conversion, wherein data encoded using an$[n^{I}, k^{I}]$initial code has to be transformed into data encoded using an$[n^{F}, k^{F}]$final code, a resource-intensive operation. Convertible codes are a class of codes that enable efficient code conversion while maintaining other desirable properties. In this paper, we focus on the access cost of conversion (total number of code symbols accessed in the conversion process) and on an important subclass of conversions known as the merge regime (combining multiple initial codewords into a single final codeword). In this setting, explicit constructions are known for systematic access-optimal Maximum Distance Separable (MDS) convertible codes for all parameters in the merge regime. However, the existing construction for a key subset of these parameters, which makes use of Vandermonde parity matrices, requires a large field size making it unsuitable for practical applications. In this paper, we provide (1) sharper bounds on the minimum field size requirement for such codes, and (2) explicit constructions for low field sizes for several parameter ranges. In doing so, we provide a proof of super-regularity of specially designed classes of Vandermonde matrices that could be of independent interest.

Many data services tune and change redundancy configurations of files over their lifetimes to address changes in data temperature and latency requirements. Unfortunately, changing redundancy configs (transcode) is IO-intensive. The Morph cluster file system introduces new transcode-efficient redundancy schemes to minimize overheads as files progress through lifetime phases. For newly ingested data, commonly stored via 3-way replication, Morph introduces a hybrid redundancy scheme that combines a replica with an erasure-coded (EC) stripe, reducing both ingest IO and capacity overheads while enabling free transcode to EC by deleting replicas. For subsequent transcodes to wider, more space-efficient EC configs, Morph exploits Convertible Codes, which minimize data read for EC transcode, and introduces new block placement policies to maximize their effectiveness.

Private information retrieval (PIR) is a technique for a client to retrieve an item from a public database without revealing to an adversarial server the item that was queried. While multi-server PIR has been well-studied in order to obtain better communication and computation relative to single-server schemes, there are far fewer fault-tolerant PIR schemes which can remain functional even in the presence of malicious adversaries. In this paper, we present a solution that combines techniques from both the cryptography and information theory communities to design robust PIR protocols that obtain better computation, communication, and storage compared to prior state-of-the-art schemes. Our results show that our PIR protocols achieve up to 9.1× lower latency, at least 39.2× less total communication, and up to 7.3× less computation than the state-of-art robust PIR protocols for a database 4GB in size and can withstand two malicious servers, and continually outperform the robust PIR baselines for a variety of parameter configurations and failure scenarios.

Erasure codes are typically used in distributed storage systems in order to protect against failures and unavailabilities with low storage overhead. An important disadvantage of classic erasure codes (such as Reed-Solomon codes) is the high cost of repairing failures. Locally repairable codes (LRCs) reduce the repair cost at the cost of higher storage overhead. In practice, the parameters of LRCs are chosen based on several factors, such as failure rates, workloads, and budget constraints. However, encoded data is stored for long periods of time, and during that time these factors can vary, and thus the ideal parameters can change. The process of changing the code parameters on encoded data is called code conversion. The default approach to code conversion is to read all data, re-encode it, and write it back, which can be prohibitively expensive. To address this problem, we propose a new construction technique for designing LRCs that can perform code conversion at a lower cost than the default approach. We apply this technique to design codes for several code conversion scenarios which are of practical interest.

Erasure codes have become an integral part of distributed storage systems as a tool for providing data reliability and durability under the constant threat of device failures. In such systems, an$[n, k]$code over a finite field$\mathbb {F}_{q}$encodes$k$message symbols from$\mathbb {F}_{q}$into$n$codeword symbols from$\mathbb {F}_{q}$which are then stored on$n$different nodes in the system. Recent work has shown that significant savings in storage space can be obtained by tuning$n$and$k$to variations in device failure rates. Such a tuning necessitatescode conversion: the process of converting already encoded data under an initial$[n^{ I}, k^{ I}]$code to its equivalent under a final$[n^{ F}, k^{ F}]$code. The default approach to conversion is to re- encode the data under the new code, which places significant burden on system resources.Convertible codesare a recently proposed class of codes for enabling resource-efficient conversions. Existing work on convertible codes has focused on minimizing the access cost, i.e., the number of code symbols accessed during conversion. Bandwidth, which corresponds to the amount of data read and transferred, is another important resource to optimize during conversions. In this paper, we study the fundamental limits on bandwidth used during code conversion and present constructions for bandwidth-optimal convertible codes. First, we model the code conversion problem using network information flow graphs with variable capacity edges. Second, focusing on MDS codes and an important parameter regime called the merge regime, we derive tight lower bounds on conversion bandwidth. The derived bounds show that conversion bandwidth can be significantly reduced as compared to the default approach even in regions where it has been shown that access cost cannot be reduced. Third, we present a new construction for MDS convertible codes which matches the proposed lower bound and is thus bandwidth-optimal during conversion.

Distributed storage systems must store large amounts of data over long periods of time. To avoid data loss due to device failures, an [n, k] erasure code is used to encode k data symbols into a codeword of n symbols that are stored across different devices. However, device failure rates change throughout the life of the data, and tuning n and k according to these changes has been shown to save significant storage space. Code conversion is the process of converting multiple codewords of an initial [nI, kI] code into codewords of a final [nF, kF] code that decode to the same set of data symbols. In this paper, we study conversion bandwidth, defined as the total amount of data transferred between nodes during conversion. In particular, we consider the case where the initial and final codes are MDS and a single initial codeword is split into several final codewords (kI= λFkFfor integer λF≥ 2), called the split regime. We derive lower bounds on the conversion bandwidth in the split regime and propose constructions that significantly reduce conversion bandwidth and are optimal for certain parameters.An extended version of this paper is available at [1].

Erasure codes are essential for providing efficient resilience against node failures in distributed storage. Typically, an$[n, k]$erasure code encodes$k$symbols into$n$symbols which are then stored in different nodes. Recent work by Kadekodi et al. shows that the failure rates of storage nodes vary significantly over time, and that changing the rate of the code (via a change in$n$and$k$) in response to such variations provides substantial storage space savings. However, the resource overhead of re-encoding the already encoded data is prohibitively high. We present a new theoretical framework formalizingcode conversion—the process of converting data encoded with an$[n^{ I}, k^{ I}]$code into data encoded with an$[{n^{ F}}, {k^{ F}}]$code while maintaining desired decodability properties. We then introduceconvertible codes, a new class of codes that allow for code conversions in a resource-efficient manner. This paper begins the study on convertible codes by focusing on linear MDS codes and the access cost of conversion. We derive a lower bound on the access cost of conversion and present an explicit optimal construction matching this bound for an important subclass of conversions. Additionally, we propose constructions with low field-size requirement for a broad subset of parameters. Our results show that it is possible to achieve code conversions with significantly less resources than the default approach of re-encoding for a wide range of parameters.

In distributed storage systems, an [$n, k$] code encodes$k$message symbols into$n$codeword symbols which are then stored on$n$nodes in the system. Recent work has shown that significant savings in storage space can be obtained by tuning$n$and$k$to variations in device failure rates. Such tuning necessitates code conversion: the process of converting data encoded under an [$n^{I}, k^{I}$] code to its equivalent under an [$n^{F}, k^{F}$] code. The default approach for code conversion places significant burden on system resources. Convertible codes are a recently proposed class of codes for enabling resource-efficient conversions. Existing work on convertible codes has focused on minimizing access cost, i.e., the number of nodes accessed during conversion. Bandwidth, which corresponds to the amount of data read and transferred, is another important resource to optimize during conversions. In this paper, we initiate the study on the fundamental limits on conversion bandwidth and present constructions for conversion-bandwidth optimal convertible codes. First, we model the code conversion problem using information flow graphs with variable capacity edges. Second, focusing on MDS codes and an important subclass of convertible codes, we derive a lower bound on conversion bandwidth. The derived bound shows that conversion bandwidth can be significantly reduced even in regimes where access cost of conversion cannot be reduced. Third, we present an explicit construction for MDS convertible codes which match this lower bound and are thus conversion-bandwidth optimal.

Distributed storage systems typically use erasure codes to provide tolerance against node failures. An erasure code encodes a message into a codeword made up of several symbols, which are then distributed among nodes in the system. Maximum distance separable (MDS)$[n, k]$scalar codes are commonly used in practice, which have the property that any subset of$k$out of$n$nodes is enough to decode the message. However, in applications such as geo-distributed storage systems, decodability from many of these subsets is unnecessary. In this paper, we study codes where only certain subsets of nodes, named access sets, are required to satisfy decodability. Our analysis focuses on two metrics of practical importance: update cost and storage overhead. For minimizing these metrics, we show that it is necessary to employ irregular array codes. We derive a lower bound on update cost as a function of the required access sets and show that it is achievable. Existing work provides an achievable lower bound on storage overhead. While both lower bounds are individually achievable, we show that they are not simultaneously achievable in general. Due to the premium in wide-area network bandwidth cost over storage cost, we focus on codes with minimum update cost (termed MUC). Finally, we derive a lower bound on the storage overhead of MUC codes and show the existence of MUC codes meeting this lower bound via a randomized construction. Our results thus show that it is possible to achieve significant savings in update cost and storage overhead by tailoring the design of codes to the required access sets.

Erasure codes are typically used in large-scale distributed storage systems to provide durability of data in the face of failures. In this setting, a set of k blocks to be stored is encoded using an [n, k] code to generate n blocks that are then stored on different storage nodes. A recent work by Kadekodi et al. [Kadekodi et al., 2019] shows that the failure rate of storage devices vary significantly over time, and that changing the rate of the code (via a change in the parameters n and k) in response to such variations provides significant reduction in storage space requirement. However, the resource overhead of realizing such a change in the code rate on already encoded data in traditional codes is prohibitively high. Motivated by this application, in this work we first present a new framework to formalize the notion of code conversion - the process of converting data encoded with an [n^I, k^I] code into data encoded with an [n^F, k^F] code while maintaining desired decodability properties, such as the maximum-distance-separable (MDS) property. We then introduce convertible codes, a new class of code pairs that allow for code conversions in a resource-efficient manner. For an important parameter regime (which we call the merge regime) along with the widely used linearity and MDS decodability constraint, we prove tight bounds on the number of nodes accessed during code conversion. In particular, our achievability result is an explicit construction of MDS convertible codes that are optimal for all parameter values in the merge regime albeit with a high field size. We then present explicit low-field-size constructions of optimal MDS convertible codes for a broad range of parameters in the merge regime. Our results thus show that it is indeed possible to achieve code conversions with significantly lesser resources as compared to the default approach of re-encoding.

In large-scale distributed storage systems, erasure codes are used to achieve fault tolerance in the face of node failures. Tuning code redundancy to observed failure rates has been shown to significantly reduce storage cost. Such tuning of redundancy requires code conversion, i.e., a change in code dimension and length on already encoded data. Convertible codes [2] are a new class of codes designed to perform such conversions efficiently. The access cost of conversion is the number of nodes accessed during conversion. Existing literature has characterized the access cost of conversion of linear MDS convertible codes only for a specific and small subset of parameters. In this paper, we present lower bounds on the access cost of conversion of linear MDS codes for all valid parameters. Furthermore, we show that these lower bounds are tight by presenting an explicit construction for access-optimal linear MDS convertible codes for all valid parameters. En route, we show that, one of the degrees-of-freedom in the design of convertible codes that was inconsequential in the previously studied parameter regimes, turns out to be crucial when going beyond these regimes and adds to the challenge in the analysis and code construction. An extended version of this paper is accessible at: [1].

Rule-based information extraction has lately received a fair amount of attention from the database community, with several languages appearing in the last few years. Although information extraction systems are intended to deal with semistructured data, all language proposals introduced so far are designed to output relations, thus making them incapable of handling incomplete information. To remedy the situation, we propose to extend information extraction languages with the ability to use mappings, thus allowing us to work with documents which have missing or optional parts. Using this approach, we simplify the semantics of regex formulas and extraction rules, two previously defined methods for extracting information. We extend them with the ability to handle incomplete data, and study how they compare in terms of expressive power. We also study computational properties of these languages, focusing on the query enumeration problem, as well as satisfiability and containment.

In this paper, we propose a simple and expressive framework for adding metadata to CSV documents and their noisy variants. The framework is based on annotating parts of the document that can be later used to read, query, or exchange the data. The core of our framework is a language based on extended regular expressions that are used for selecting data. These expressions are then combined using a set of rules in order to annotate the data. We study the computational complexity of implementing our framework and present an efficient evaluation algorithm that runs in time proportional to its output and linear in its input. As a proof of concept, we test an implementation of our framework against a large number of real world datasets and show that it can be efficiently used in practice.