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.

Holographic Storage is an old idea that has always promised high density and fast random access, but has never been commercially competitive with Hard Disk Drives (HDDs) and Solid State Devices (SSDs). In Project HSD at Microsoft Research we asked the question: “Does holographic storage finally make sense for cloud storage?” This article describes our journey toward answering this question. We achieved 1.8× higher density than the previous state-of-the-art, using commodity components available today and leveraging machine learning to compensate for the noise and distortions introduced by commodity components. This uncovered two new challenges which are the focus of this article: achieving high end-to-end energy efficiency without sacrificing capacity, and spatial multiplexing without mechanical movement. Improving end-to-end energy efficiency requires joint optimization across low-level media parameters and higher-level system parameters that govern background maintenance operations such as read refresh and garbage collection. We developed new physics models of the media; analytic and simulation models of the media access and background media maintenance; and workload-driven optimization to find optimal parameter combinations. These techniques resulted in a 14× improvement over the previous approach for typical workloads without sacrificing capacity. We also designed the first scalable and mechanical movement free spatial multiplexing system for holographic storage. Despite these advances, we conclude that currently, holographic storage is still far from the combination of density, capacity scaling, and energy efficiency needed to compete with the incumbent technologies. We need fundamental advances in the physical media that improve energy efficiency by another 1–2 orders of magnitude without reducing data density. Further advances in optics are also required to achieve spatial multiplexing that is simultaneously scalable, low-loss, and high-density.

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.

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.

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

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.

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.

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.