Silent Data Corruption (SDC) poses a reliability threat in modern datacenters. These insidious errors evade detections and propagate incorrect results throughout the system. Companies including Google, Meta, and Alibaba have reported SDC incidents affecting their production. In this paper, we present the first comprehensive instruction- and application-level analysis of vector instruction SDCs in hyper-scale datacenters using a two-stage approach. We perform over 78 trillion test rounds in more than 14 billion CPU seconds. Our observations reveal undocumented SDC patterns that provide insights into possible underlying causes and inspire new mitigation strategies. Based on these findings, we propose a low-overhead SDC detection mechanism leveraging in-application algorithm-based fault tolerance. Our method achieves 88% to 100% SDC machine detection rate with a time overhead of only 1.35% even for modestly sized inputs.

Recent changes in data temperatures and storage device characteristics, both mechanical disk-drives (HDDs) and solid-state drives (SSDs), expand the set of deployment options for exascale storage. Until recently, exascale storage systems followed a pattern of placing most data on HDDs with smaller amounts of SSD storage used for caching and performance-critical workloads. Exascale storage provisioning and dataset placement trade-offs have now changed.

Recent studies have shown that distributed storage systems can achieve significant space savings by adapting redundancy levels to varying disk failure rates. This adaptation is performed via code conversion, wherein data encoded under an initial code are transformed to data encoded under a final code. While this process is typically resource-intensive, convertible codes are designed to enable these transformations efficiently while preserving desirable decodability constraints such as repair degree, or the number of nodes accessed during node repair. In this work, we focus on the bandwidth cost of conversion, or the total amount of data transferred during the conversion process. We study fundamental limits on the bandwidth cost of conversion between systematic optimal-distance Locally Repairable Codes (LRCs). We restrict our focus to the global merge regime, in which multiple initial codewords are combined to form a single final codeword while preserving information locality. We focus on stable convertible codes, wherein the number of unchanged nodes is maximized during conversion. We generalize an information-theoretic approach for modeling code conversion to the LRC setting, and derive the first non-trivial lower bounds on the bandwidth cost of conversion in this regime. Notably, our bounds do not rely on any linearity assumptions. Consequently, we show that the constructions of Maturana and Rashmi are bandwidth-optimal across a broad range of parameters in the global merge regime.

This paper introduces Helix, a distributed system for high-throughput, low-latency large language model (LLM) serving in heterogeneous GPU clusters. The key idea behind Helix is to formulate inference computation of LLMs over heterogeneous GPUs and network connections as a max-flow problem on directed, weighted graphs, whose nodes represent GPU instances and edges capture both GPU and network heterogeneity through their capacities. Helix then uses a mixed integer linear programming (MILP) algorithm to discover highly optimized strategies to serve LLMs on heterogeneous GPUs. This approach allows Helix to jointly optimize model placement and request scheduling, two highly entangled tasks in heterogeneous LLM serving. Our evaluation on several heterogeneous clusters ranging from 24 to 42 GPU nodes shows that Helix improves serving throughput by up to 3.3x and reduces prompting and decoding latency by up to 66% and 24%, respectively, compared to existing approaches. Helix is available at https://github.com/Thesys-lab/Helix-ASPLOS25.

Large-scale distributed storage systems rely on erasure codes to ensure fault tolerance against node failures. Due to the observed changing failure rates within these systems, code redundancy tuning, or code conversion has been shown to reduce storage cost. Previous work has developed theoretical bounds and constructions for convertible codes, a specialized class of erasure codes optimizing either access or bandwidth costs during conversion. In this paper, we address the challenge of securing convertible codes in the presence of an eavesdropper. We introduce an eavesdropper-secrecy model for convertible codes wherein an eavesdropper gaining read access to a subset of the codeword symbols learns nothing (information-theoretically) about the underlying message. We then focus on access-cost optimal convertible codes, and we then derive the information-theoretic upper bound on the number of message symbols that can be stored securely. Finally, we provide an explicit construction that simultaneously reaches this secrecy bound while admitting accesscost optimal conversion using concatenation of nested codes with traditional convertible codes. Since our construction works with all traditional access-optimal convertible codes, we show that access-optimal secure convertible codes exist for all message and codeword length parameters.

Coded computation is an emerging paradigm of applying coding theory to large-scale distributed computing to provide resilience against slow or otherwise unavailable workers. We propose a new approach to view coded computation via the lens of the locality of codes. We do so by defining a new notion of locality, calledcomputational locality, using the locality properties of an appropriately defined code for the function being computed. This notion of locality incorporates the unique aspects of locality arising in the context of coded computation. Our first major contribution is to demonstrate how to design a coded computation scheme for a function using the local recovery scheme of an appropriately defined code. The so-obtained scheme rederives the best known coded computation scheme for multivariate polynomial functions via the viewpoint of the locality of the Reed-Muller code. Our second major contribution is to show that the proposed locality-based approach enables new tradeoffs (e.g., communication bandwidth vs number of workers) compared to existing coded computation schemes. Specifically for the case when there is known linear dependence among inputs—common in many real-world applications—the proposed approach significantly reduces resource overhead (i.e., number of workers) without incurring any tradeoffs.

Erasure codes are critical tools for building fault-tolerant and resource-efficient storage systems. However developing and maintaining optimized erasure-coding libraries are challenging. We make the case that the growth of fast machine-learning (ML) libraries may serve as a lifeboat for easing the development of current and future optimized erasure-coding libraries: fast erasure-coding libraries for various hardware platforms can be easily implemented by using existing optimized ML libraries. We show that the computation structure of many erasure codes mirrors that common to matrix multiplication, which is heavily optimized in ML libraries. Due to this similarity, one can implement erasure codes using ML libraries in few lines of code and with little knowledge of erasure codes, while immediately adopting the many optimizations within these libraries, without requiring expertise in high-performance programming. We develop prototypes of our proposed approach using an existing ML library. Our prototypes are up to 1.75× faster than state-of-the-art custom erasure-coding libraries.

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.

LRU has been the basis of cache eviction algorithms for decades, with a plethora of innovations on improving LRU's miss ratio and throughput. While it is well-known that FIFO-based eviction algorithms provide significantly better throughput and scalability, they lag behind LRU on miss ratio, thus, cache efficiency.

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.

Large-scale computations are ubiquitous and demand exorbitant resources, with matrix multiplication being a prominent example. Multiplying high-dimensional matrices is cumbersome for an individual server but is frequently needed in many applications. To alleviate the computational cost, one can take a low-rank approximation of the matrix product and distribute it over multiple workers. However, the tail latency of such distributed computations is degraded by straggling workers. One solution is to query extra workers with coded inputs to replace the outputs of straggling workers; this technique is called "coded computing." Nearly all existing coded computing schemes apply to multiplying any matrices. Instead, we propose a new framework to design coded computing schemes to take advantage of the structure induced by compression, which we call compression-informed coded computing. We then showcase the benefits of the framework in two steps. First, we illustrate how sketching can lead to linear dependencies in the matrices multiplied by the workers. Second, we apply locality-based coded computing to leverage these linear dependencies to make do with fewer workers compared to coded computing schemes that ignore the structure of the matrices being multiplied.

The tail latency of large-scale distributed computations, such as matrix multiplication, is adversely affected by unavailable workers. A technique called "coded computation" alleviates this problem by using extra workers to evaluate the function being computed at coded inputs and substitute the extra workers for the unavailable ones. Most of the literature on coded computation of multivariate polynomials applies to arbitrary inputs and ignores the structure of the inputs. However, a recent work introduced a locality-based coded computation framework and showed how to leverage the structure of inputs to reduce the overhead of coded computation. Our work expands the toolkit of locality-based approaches to coded computation beyond linearly dependent input points for the class of m-homogeneous polynomials. Specifically, we present new methods to exploit the structure of each coordinate of the inputs. Finally, we apply our new tools to multiplying upper (or lower) triangular matrices and show a reduction in the number of workers needed compared to the best known coded computation schemes.

Recovering bursts of lost packets in real-time is crucial to multimedia live-streaming applications’ quality-of-experience (QoE). Streaming codes optimally handle the unique aspects of loss recovery for live streaming, including (a) variable-size messages, (b) a real-time playback deadline, and (c) burst losses across multiple frames. However, existing models for streaming codes in this setting only apply to bursts that drop all data sent for each message. Yet in many real-world applications only some packets are lost for each message in what we call a "partial burst." We introduce a new streaming model to accommodate partial bursts. We then design a building block to construct a streaming code given any choice of how much parity to allocate for each message. Next, we present a streaming code in an offline setting (i.e., where the sizes of future messages are known) by combining (a) the building block with (b) a linear program to set the number of parity symbols per message. We then design a streaming code in an online setting (i.e., without knowledge of the future) by combining (a) the building block with (b) a learning-augmented algorithm to set the number of parity symbols per message. The constructions are approximately rate-optimal under a natural condition on the nature of feedback.

As a cache eviction algorithm, FIFO has a lot of attractive properties, such as simplicity, speed, scalability, and flash-friendliness. The most prominent criticism of FIFO is its low efficiency (high miss ratio).

Deep-learning-based recommendation models (DLRMs) are widely deployed to serve personalized content. In addition to using neural networks, DLRMs have large, sparsely-accessed embedding tables, which map categorical features to a learned dense representation. Due to the large sizes of embedding tables, DLRM training is typically distributed across the memory of tens or hundreds of nodes. Node failures are common in such large systems and must be mitigated to enable training to complete within production deadlines. Checkpointing is the primary approach used for fault tolerance in these systems, but incurs significant time overhead both during normal operation and when recovering from failures. As these overheads increase with DLRM size, checkpointing is slated to become an even larger overhead for future DLRMs, which are expected to grow. This calls for rethinking fault tolerance in DLRM training. We present ECRec, a DLRM training system that achieves efficient fault tolerance by coupling erasure coding with the unique characteristics of DLRM training. ECRec takes a hybrid approach between erasure coding and replicating different DLRM parameters, correctly and efficiently updates redundant parameters, and enables training to proceed without pauses, while maintaining the consistency of the recovered parameters. We implement ECRec atop XDL, an open-source, industrial-scale DLRM training system. Compared to checkpointing, ECRec reduces training-time overhead on large DLRMs by up to 66%, recovers from failure up to 9.8× faster, and continues training during recovery with only a 7--13% drop in throughput (whereas checkpointing must pause).

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.

One pervasive challenge in providing a high quality-of-service for live communication is to recover lost packets in real-time. Streaming codes are a class of erasure codes that are designed for such strict, low-latency streaming communication settings. Motivated by applications that transmit messages whose sizes vary over time, such as live video streaming, this paper considers the setting of streaming codes under variable-size messages. In practice, streaming codes operate in an “online” setting where the sizes of the future messages are unknown. “Offline” codes, in contrast, have access to the sizes of all messages, including future ones. This paper introduces the first online rate-optimal streaming codes for communicating over a burst-only packet loss channel for two broad parameter regimes. These two online codes match the rates of optimal offline codes for the two settings despite the apparent advantage of the offline setting. This paper further establishes that online codes cannot attain the optimal rate for offline codes for all remaining parameter settings.

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].

Real-time streaming communication requires a high quality-of-service despite contending with packet loss. Streaming codes are a class of codes best suited for this setting. A key challenge for streaming codes is that they operate in an "online" setting in which the amount of data to be transmitted varies over time and is not known in advance. Mitigating the adverse effects of variability requires spreading the data that arrives at a time slot over multiple future packets, and the optimal strategy for spreading depends on the arrival pattern. Algebraic coding techniques alone are therefore insufficient for designing rate-optimal codes. We combine algebraic coding techniques with a learning-augmented algorithm for spreading to design the first approximately rate-optimal streaming codes for a range of parameter regimes that are important for practical applications. 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.

Live communication is ubiquitous, and frequently must contend with reliability issues due to packet loss during transmission. The effect of packet losses can be alleviated by using erasure codes, which aid in recovering lost packets. Streaming codes are a class of codes designed for the live communication setting, which encode a stream of message packets arriving sequentially for transmission over a packet-loss channel. The existing study of streaming codes considers settings where the sizes of the message packets to be transmitted are all fixed. However, message packets occur with unpredictable and variable sizes in many applications, such as videoconferencing. In this paper, we present a generalized model for streaming codes that incorporates message packets of variable sizes. We show that the variability in the sizes of message packets induces a new trade-off between the rate and the decoding delay under lossless transmission. Moreover, the variability in the sizes of message packets impacts the optimal rate of transmission. To address this, we introduce algorithms to compute upper and lower bounds on the optimal rate for any given sequence of sizes of message packets. We then design an explicit streaming code for the proposed model. We empirically evaluate the code construction over a live video trace for several representative parameter settings, and show that the rate of the construction is approximately 90% of an upper bound and 5%–48% higher than naively using the existing streaming codes.

Datacenter vision systems widely use small, specialized convolutional neural networks (CNNs) trained on specific tasks for high-throughput inference. These settings employ accelerators with massive computational capacity, but which specialized CNNs underutilize due to having low arithmetic intensity. This results in suboptimal application-level throughput and poor returns on accelerator investment. Increasing batch size is the only known way to increase both application-level throughput and accelerator utilization for inference, but yields diminishing returns; specialized CNNs poorly utilize accelerators even with large batch size. We propose FoldedCNNs, a new approach to CNN design that increases inference throughput and utilization beyond large batch size. FoldedCNNs rethink the structure of inputs and layers of specialized CNNs to boost arithmetic intensity: in FoldedCNNs, f images with C channels each are concatenated into a single input with fC channels and jointly classified by a wider CNN. Increased arithmetic intensity in FoldedCNNs increases the throughput and GPU utilization of specialized CNN inference by up to 2.5x and 2.8x, with accuracy close to the original CNN in most cases.

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.

Coded computation is an emerging paradigm for robustness in large-scale distributed computing, which applies principles from coding theory to provide robustness against slow or otherwise unavailable workers. We propose a new approach to view coded computation via the lens of locality of codes. We do so by defining a new notion of locality, called computational locality, via the locality properties of an appropriately defined code for the function being computed. This notion of locality incorporates the unique aspects of locality arising in the context of coded computation. Using this new approach, (1) We demonstrate how to design a coded computation scheme for a function using the local decoding scheme of an appropriately defined code. This rederives the best-known coded computation scheme for multivariate polynomial functions via the viewpoint of locality of the Reed Muller code. (2) We show that the proposed locality-based approach enables coded computation schemes with significantly lower resource overhead than existing schemes. Specifically, matrix multiplication over complex numbers, a common workload in high performance computing, is achieved with 33.3% fewer workers than state-of-the-art coded computation schemes.

Neural networks (NNs) are increasingly employed in safety-critical domains and in environments prone to unreliability (e.g., soft errors), such as on spacecraft. Therefore, it is critical to impart fault tolerance to NN inference. Algorithm-based fault tolerance (ABFT) is emerging as an efficient approach for fault tolerance in NNs. We propose an adaptive approach to ABFT for NN inference that exploits untapped opportunities in emerging deployment scenarios. GPUs have high compute-to-memory-bandwidth ratios, while NN layers have a wide range of arithmetic intensities. This leaves some layers compute bound and others memory-bandwidth bound, but current approaches to ABFT do not consider these differences. We first investigate ABFT schemes best suited for each of these scenarios. We then propose intensity-guided ABFT, an adaptive, arithmetic-intensity-guided approach that selects the most efficient ABFT scheme for each NN layer. Intensity-guided ABFT reduces execution-time overhead by 1.09--5.3$\times$ across many NNs compared to traditional approaches to ABFT.

Modern web services use in-memory caching extensively to increase throughput and reduce latency. There have been several workload analyses of production systems that have fueled research in improving the effectiveness of in-memory caching systems. However, the coverage is still sparse considering the wide spectrum of industrial cache use cases. In this work, we significantly further the understanding of real-world cache workloads by collecting production traces from 153 in-memory cache clusters at Twitter, sifting through over 80 TB of data, and sometimes interpreting the workloads in the context of the business logic behind them. We perform a comprehensive analysis to characterize cache workloads based on traffic pattern, time-to-live (TTL), popularity distribution, and size distribution. A fine-grained view of different workloads uncover the diversity of use cases: many are far more write-heavy or more skewed than previously shown and some display unique temporal patterns. We also observe that TTL is an important and sometimes defining parameter of cache working sets. Our simulations show that ideal replacement strategy in production caches can be surprising, for example, FIFO works the best for a large number of workloads.

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].

Providing high quality-of-service for live communication is a pervasive challenge which is plagued by packet losses during transmission. Streaming codes are a class of erasure codes specifically designed for such low-latency streaming communication settings. We consider the recently proposed setting of streaming codes under variable-size messages which reflects the requirements of applications such as live video streaming. In practice, streaming codes often need to operate in an "online" setting where the sizes of the future messages are unknown. Yet, previously studied upper bounds on the rate apply to "offline" coding schemes with access to all (including future) message sizes.In this paper, we evaluate whether the optimal offline rate is a feasible goal for online streaming codes when communicating over a burst-only packet loss channel. We identify two broad parameter regimes where, perhaps surprisingly, online streaming codes can, in fact, match the optimal offline rate. For both of these settings, we present rate-optimal online code constructions. For all remaining parameter settings, we establish that it is impossible for online schemes to attain the optimal offline rate.

Social live video streaming (SLVS) applications are becoming increasingly popular with the rise of platforms such as Facebook-Live, YouTube-Live, Twitch and Periscope. A key characteristic that differentiates this new class of applications from traditional live streaming is that these live streams are watched by viewers at different delays; while some viewers watch a live stream in real-time, others view the content in a time-shifted manner at different delays. In the presence of variability in the upload bandwidth, which is typical in mobile environments, existing solutions silo viewers into either receiving low latency video at a lower quality or a higher quality video with a significant delay penalty, without accounting for the presence of diverse time-shifted viewers.

Machine learning models are becoming the primary work-horses for many applications. Services deploy models through prediction serving systems that take in queries and return predictions by performing inference on models. Prediction serving systems are commonly run on many machines in cluster settings, and thus are prone to slowdowns and failures that inflate tail latency. Erasure coding is a popular technique for achieving resource-efficient resilience to data unavailability in storage and communication systems. However, existing approaches for imparting erasure-coded resilience to distributed computation apply only to a severely limited class of functions, precluding their use for many serving workloads, such as neural network inference.

Repair operations in erasure-coded distributed storage systems involve a lot of data movement. This can potentially expose data to malicious acts of passive eavesdroppers or active adversaries, putting security of the system at risk. This paper presents coding schemes and repair algorithms that ensure security of the data in the presence of passive eavesdroppers and active adversaries while maintaining high availability, reliability, and resource efficiency in the system. The proposed codes are optimal in that they meet previously proposed lower bounds on storage and network-bandwidth requirements for a wide range of system parameters. The results thus establish the secure storage capacity of such systems. The proposed codes are based on an optimal class of codes called product-matrix codes. The constructions presented for security from active adversaries provide an additional appealing feature of “on-demand security,” where the desired level of security can be chosen separately for each instance of repair, and the proposed algorithms remain optimal simultaneously for all possible security levels. This paper also provides necessary and sufficient conditions governing the transformation of any (non-secure) code into one providing on-demand security.

Erasure codes are being extensively deployed in distributed storage systems instead of replication to achieve fault tolerance in a storage efficient manner. While traditional erasure codes are storage efficient, they can result in a significant increase in the amount of data access and downloaded during rebuilding of failed or otherwise unavailable nodes. In this paper, we present a new framework, which we call piggybacking, for constructing distributed storage codes that are efficient in the amount of data read and downloaded during rebuilding, while meeting requirements arising out of system considerations in data centers-maximum-distance-separability (MDS), high-rate, and a small number of so-called substripes. Under this setting, to the best of our knowledge, piggyback codes achieve the minimum average amount of data access and downloaded during rebuilding among all existing explicit solutions. The piggybacking framework also offers a rich design space for constructing codes for a variety of other settings. In particular, we construct codes that require minimum amount of data access and downloaded for rebuilding among all existing solutions for: 1) binary MDS array codes with more than two parities and 2) MDS codes with the smallest locality during rebuilding. In addition, we show how piggybacking can be employed to enable efficient repair of parity nodes in codes that address the rebuilding of only systematic nodes. The basic idea behind the piggybacking framework is to take multiple instances of existing codes and add carefully designed functions of the data from one instance to the others. This framework provides 25% to 50% savings in the average amount of data access and downloaded during rebuilding depending on the choice of the code parameters.

We consider the problem of constructing explicit erasure codes for distributed storage with the following desirable properties motivated by system constraints: (i) Maximum-Distance-Separable (MDS), (ii)Optimal repair-bandwidth, (iii)Flexibility in repair (as will be described), (iv) Systematic Form, and (v) Fast encoding (enabled by a sparse generator matrix). Existing constructions in the literature satisfy only strict subsets of these desired properties. This paper presents the first explicit code construction which theoretically guarantees all the five desired properties simultaneously. We first present a construction that builds on Product-Matrix (PM) codes by enabling sparsity in its generator matrix. We then present a transformation for general classes of storage and repair optimal codes to enable fast encoding through sparsity. In practice, such sparse codes are roughly 7 times sparser than their standard counterparts, and result in encoding speedup by a factor of about 4 for typical parameters.

MART, an ensemble model of boosted regression trees, is known to deliver high prediction accuracy for diverse tasks, and is widely used in practice. However, it suffers an issue which we call over-specialization, wherein trees added at later iterations tend to impact the prediction of only a few instances, and make negligible contribution towards the remaining instances. This negatively affects the performance of the model on unseen data, and also makes the model over-sensitive to the contributions of the few, initially added tress. We show that the commonly used tool to address this issue, that of shrinkage, alleviates the problem only to a certain extent and the fundamental issue of over-specialization still remains. In this work, we explore a different approach to address the problem, that of employing dropouts, a tool that has been recently proposed in the context of learning deep neural networks. We propose a novel way of employing dropouts to tackle the issue of over-specialization in MART, resulting in the DART algorithm. We evaluate DART on ranking, regression and classification tasks, using large scale, publicly available datasets, and show that DART outperforms MART in each of the tasks, with a significant margin.

In distributed storage systems, storage nodes intermittently go offline for numerous reasons. On coming back online, nodes need to update their contents to reflect any modifications to the data in the interim. In this paper, we consider a setting where no information regarding modified data needs to be logged in the system. In such a setting, a `stale' node needs to update its contents by downloading data from already updated nodes, while neither the stale node nor the updated nodes have any knowledge as to which data symbols are modified and what their value is. We investigate the fundamental limits on the amount of communication necessary for such an oblivious update process. We first present a generic lower bound on the amount of communication that is necessary under any storage code with a linear encoding (while allowing non-linear update protocols). This lower bound is derived under a set of extremely weak conditions, giving all updated nodes access to the entire modified data and the stale node access to the entire stale data as side information. We then present codes and update algorithms that are optimal in that they meet this lower bound. Next, we present a lower bound for an important subclass of codes, that of linear Maximum-Distance-Separable (MDS) codes. We then present an MDS code construction and an associated update algorithm that meets this lower bound. These results thus establish the capacity of oblivious updates in terms of the communication requirements under these settings.

Private information retrieval (PIR) systems allow a user to retrieve a record from a public database without revealing to the server which record is being retrieved. The literature on PIR considers only replication-based systems, wherein each storage node stores a copy of the entire data. However, systems based on erasure codes are gaining increasing popularity due to a variety of reasons. This paper initiates an investigation into PIR in erasure-coded systems by establishing its capacity and designing explicit codes and algorithms. The notion of privacy considered here is information-theoretic, and the metric optimized is the amount of data downloaded by the user during PIR. In this paper, we present four main results. First, we design an explicit erasure code and PIR algorithm that requires only one extra bit of download to provide perfect privacy. In contrast, all existing PIR algorithms require a download of at least twice the size of the requisite data. Second, we derive lower bounds proving the necessity of downloading at least one additional bit. This establishes the precise capacity of PIR with respect to the metric of download. These results are also applicable to PIR in replication-based systems, which are a special case of erasure codes. Our third contribution is a negative result showing that capacity-achieving codes necessitate super-linear storage overheads. This motivates the fourth contribution of this paper: an erasure code and PIR algorithm that requires a linear storage overhead, provides high reliability to the data, and is a small factor away from the capacity.

Erasure codes such as Reed-Solomon (RS) codes are being extensively deployed in data centers since they offer significantly higher reliability than data replication methods at much lower storage overheads. These codes however mandate much higher resources with respect to network bandwidth and disk IO during reconstruction of data that is missing or otherwise unavailable. Existing solutions to this problem either demand additional storage space or severely limit the choice of the system parameters. In this paper, we present "Hitchhiker", a new erasure-coded storage system that reduces both network traffic and disk IO by around 25% to 45% during reconstruction of missing or otherwise unavailable data, with no additional storage, the same fault tolerance, and arbitrary flexibility in the choice of parameters, as compared to RS-based systems. Hitchhiker 'rides' on top of RS codes, and is based on novel encoding and decoding techniques that will be presented in this paper. We have implemented Hitchhiker in the Hadoop Distributed File System (HDFS). When evaluating various metrics on the data-warehouse cluster in production at Facebook with real-time traffic and workloads, during reconstruction, we observe a 36% reduction in the computation time and a 32% reduction in the data read time, in addition to the 35% reduction in network traffic and disk IO. Hitchhiker can thus reduce the latency of degraded reads and perform faster recovery from failed or decommissioned machines.

We present a new piggybacking framework for designing distributed storage codes that are efficient in the amount of data read and downloaded during node-repair. We illustrate the power of this framework by constructing explicit codes that attain the smallest amount of data to be read and downloaded for repair among all existing solutions for three important settings: (a) codes meeting the constraints of being maximum distance separable (MDS), high-rate, and having a small number of substripes, (b) binary MDS codes for all parameters where binary MDS codes exist, and (c) MDS codes with the smallest repair-locality. In addition, we show how to use this framework to enable efficient repair of parity nodes in existing codes that are constructed to address the repair of only the systematic nodes. The basic idea behind this framework is to take multiple stripes of existing codes and add carefully designed functions of the data of one stripe to other stripes. Typical savings in the amount of data read and downloaded during repair are 25% to 50% depending on the choice of the system parameters.

Shamir's (n, k) threshold secret sharing is an important component of several cryptographic protocols, such as those for secure multiparty-computation. These protocols typically assume the presence of direct communication links from the dealer to all participants, in which case the dealer can directly pass the shares of the secret to every participant. In this paper, we consider the problem of secret sharing when the dealer does not have direct communication links to all participants, and instead, they form a general network. We present an algorithm for secret sharing over networks that satisfy what we call the k-propagating-dealer condition. The algorithm is communication-efficient, distributed and deterministic. Interestingly, the solution constitutes an instance of a network coding problem admitting a distributed and deterministic solution, and furthermore, handles the case of nodal-eavesdropping, about which very little appears to be known in the literature. In the second part of the paper, we derive information-theoretic lower bounds on the communication complexity of secret sharing over any network, which may also be of independent interest. We show that for networks satisfying the k-propagating-dealer condition, the communication complexity of our algorithm is Θ(n), and furthermore, is always within a constant factor of the lower bound. We also show that, in contrast, existing solutions in the literature entail a communication-complexity that is superlinear for a wide class of networks, and is Θ(n2) in the worst case. Our algorithm thus allows for efficient generalization of several cryptographic protocols to a large class of networks.

Regenerating codes are a class of codes proposed for providing reliability of data and efficient repair of failed nodes in distributed storage systems. In this paper, we address the fundamental problem of handling errors and erasures at the nodes or links, during the data-reconstruction and node-repair operations. We provide explicit regenerating codes that are resilient to errors and erasures, and show that these codes are optimal with respect to storage and bandwidth requirements. As a special case, we also establish the capacity of a class of distributed storage systems in the presence of malicious adversaries. While our code constructions are based on previously constructed Product-Matrix codes, we also provide necessary and sufficient conditions for introducing resilience in any regenerating code.

Regenerating codes are a class of recently developed codes for distributed storage that, like Reed-Solomon codes, permit data recovery from any subset of nodes within the -node network. However, regenerating codes possess in addition, the ability to repair a failed node by connecting to an arbitrary subset of nodes. It has been shown that for the case of functional repair, there is a tradeoff between the amount of data stored per node and the bandwidth required to repair a failed node. A special case of functional repair is exact repair where the replacement node is required to store data identical to that in the failed node. Exact repair is of interest as it greatly simplifies system implementation. The first result of this paper is an explicit, exact-repair code for the point on the storage-bandwidth tradeoff corresponding to the minimum possible repair bandwidth, for the case when . This code has a particularly simple graphical description, and most interestingly has the ability to carry out exact repair without any need to perform arithmetic operations. We term this ability of the code to perform repair through mere transfer of data as repair by transfer. The second result of this paper shows that the interior points on the storage-bandwidth tradeoff cannot be achieved under exact repair, thus pointing to the existence of a separate tradeoff under exact repair. Specifically, we identify a set of scenarios which we term as “helper node pooling,” and show that it is the necessity to satisfy such scenarios that overconstrains the system.

Regenerating codes are a class of recently developed codes for distributed storage that, like Reed-Solomon codes, permit data recovery from any arbitrary$k$of$n$nodes. However regenerating codes possess in addition, the ability to repair a failed node by connecting to any arbitrary$d$nodes and downloading an amount of data that is typically far less than the size of the data file. This amount of download is termed the repair bandwidth. Minimum storage regenerating (MSR) codes are a subclass of regenerating codes that require the least amount of network storage; every such code is a maximum distance separable (MDS) code. Further, when a replacement node stores data identical to that in the failed node, the repair is termed as exact.

Regenerating codes are a class of codes for distributed storage networks that provide reliability and availability of data, and also perform efficient node repair. Another important aspect of a distributed storage network is its security. In this paper, we consider a threat model where an eavesdropper may gain access to the data stored in a subset of the storage nodes, and possibly also, to the data downloaded during repair of some nodes. We provide explicit constructions of regenerating codes that achieve information-theoretic secrecy capacity in this setting.

Erasure codes are an efficient means of storing data across a network in comparison to data replication, as they tend to reduce the amount of data stored in the network and offer increased resilience in the presence of node failures. The codes perform poorly though, when repair of a failed node is called for, as they typically require the entire file to be downloaded to repair a failed node. A new class of erasure codes, termed as regenerating codes were recently introduced, that do much better in this respect. However, given the variety of efficient erasure codes available in the literature, there is considerable interest in the construction of coding schemes that would enable traditional erasure codes to be used, while retaining the feature that only a fraction of the data need be downloaded for node repair. In this paper, we present a simple, yet powerful, framework that does precisely this. Under this framework, the nodes are partitioned into two types and encoded using two codes in a manner that reduces the problem of node-repair to that of erasure-decoding of the constituent codes. Depending upon the choice of the two codes, the framework can be used to avail one or more of the following advantages: simultaneous minimization of storage space and repair-bandwidth, low complexity of operation, fewer disk reads at helper nodes during repair, and error detection and correction.

Regenerating codes are a class of distributed storage codes that allow for efficient repair of failed nodes, as compared to traditional erasure codes. An$[n, k, d]$regenerating code permits the data to be recovered by connecting to any$k$of the$n$nodes in the network, while requiring that a failed node be repaired by connecting to any$d$nodes. The amount of data downloaded for repair is typically much smaller than the size of the source data. Previous constructions of exact-regenerating codes have been confined to the case$n=d+1$. In this paper, we present optimal, explicit constructions of (a) Minimum Bandwidth Regenerating (MBR) codes for all values of$[n, k, d]$and (b) Minimum Storage Regenerating (MSR) codes for all$[n, k, d\geq 2k-2]$, using a new product-matrix framework. The product-matrix framework is also shown to significantly simplify system operation. To the best of our knowledge, these are the first constructions of exact-regenerating codes that allow the number$n$of nodes in the network, to be chosen independent of the other parameters. The paper also contains a simpler description, in the product-matrix framework, of a previously constructed MSR code with$[n=d+1, k, d\geq 2k-1]$.

In the distributed storage setting that we consider, data is stored across n nodes in the network such that the data can be recovered by connecting to any subset of k nodes. Additionally, one can repair a failed node by connecting to any d nodes while downloading β units of data from each. Dimakis et al. show that the repair bandwidth dβ can be considerably reduced if each node stores slightly more than the minimum required and characterize the tradeoff between the amount of storage per node and the repair bandwidth. In the exact regeneration variation, unlike the functional regeneration, the replacement for a failed node is required to store data identical to that in the failed node. This greatly reduces the complexity of system maintenance. The main result of this paper is an explicit construction of codes for all values of the system parameters at one of the two most important and extreme points of the tradeoff the Minimum Bandwidth Regenerating point, which performs optimal exact regeneration of any failed node. A second result is a non-existence proof showing that with one possible exception, no other point on the tradeoff can be achieved for exact regeneration.

In the distributed storage setting introduced by Dimakis et al., B units of data are stored across n nodes in the network in such a way that the data can be recovered by connecting to any k nodes. Additionally one can repair a failed node by connecting to any d nodes while downloading at most β units of data from each node. In this paper, we introduce a flexible framework in which the data can be recovered by connecting to any number of nodes as long as the total amount of data downloaded is at least B. Similarly, regeneration of a failed node is possible if the new node connects to the network using links whose individual capacity is bounded above by βmaxand whose sum capacity equals or exceeds a predetermined parameter γ. In this flexible setting, we obtain the cut-set lower bound on the repair bandwidth along with a constructive proof for the existence of codes meeting this bound for all values of the parameters. An explicit code construction is provided which is optimal in certain parameter regimes.