Michael Luby

Michael Luby

We introduce FLUID (Fountain LiqUId Delivery), a protocol that uses fountain coding and receiver feedback for low-latency delivery of data blocks over lossy networks. Idealized Automatic Repeat reQuest (ARQ) protocols are bandwidth-optimal in the single-path setting, but must deliver every packet in a block and therefore can require additional rounds under packet loss. FLUID uses a controlled amount of slack to relax this all-packets requirement, allowing delivery to finish once enough encoded packets have been received. This yields substantially tighter delivery latency while remaining deterministically close to the ARQ bandwidth optimum. FLUID is controlled by a slack parameter $ε$. Under the Loss-Product Rule, delivery finishes once the product of packet loss fractions across transmission rounds falls below $ε$. Thus, FLUID can finish delivery in a small number of rounds even when every round experiences packet loss, while $ε$ controls the gap between FLUID and bandwidth-optimal ARQ.

Michael Luby

Applications such as cloud gaming, video streaming, telemetry, ML inference, and data transfer provide a better experience when data is released at the receiver with timing reflecting how the data enters the sender. In practice, network delay variation and recovery dynamics at the receiver distort this timing even when transports deliver all packets correctly, producing visible jitter, stalls, and unstable playback. Many such applications operate best when delivery preserves this timing behavior and its implied order; out-of-order or irregular delivery can significantly degrade performance even when all data eventually arrives. We present a lightweight receiver-side release scheduling protocol, Adaptive Release Control (ARC), that restores this timing at the receiver. ARC releases recovered data in a manner that follows the sender's timing, maintaining ordering and limiting reordering when necessary while producing smooth delivery with minimal added latency given network conditions. It operates entirely on the receiver clock and requires no feedback, synchronization, or changes to the underlying transport. As an example, we integrate ARC into LT3, a network-layer system currently deployed as a software overlay that forwards traffic without altering the transport protocols it carries, where ARC functions as an independent module that regulates release timing for forwarded data. Evaluating LT3 with ARC on a cloud-gaming workload shows that the protocol removes virtually all large jitter excursions and yields release intervals that closely match the sender's timing, translating into improved perceptual smoothness. Broader latency improvements arise from the behavior of the full LT3 system. The benefits of ARC extend to transport protocols carried over LT3, including TCP, QUIC, WebRTC, UDP, and RTP, as preserving sender timing improves their behavior across a wide range of conditions.

Michael Luby, Thomas Richardson

One of the primary objectives of a distributed storage system is to reliably store large amounts of source data for long durations using a large number $N$ of unreliable storage nodes, each with $c$ bits of storage capacity. Storage nodes fail randomly over time and are replaced with nodes of equal capacity initialized to zeroes, and thus bits are erased at some rate $e$. To maintain recoverability of the source data, a repairer continually reads data over a network from nodes at an average rate $r$, and generates and writes data to nodes based on the read data. The distributed storage source capacity is the maximum amount of source that can be reliably stored for long periods of time. Previous research shows that asymptotically the distributed storage source capacity is at most $\left(1-\frac{e}{2 \cdot r}\right) \cdot N \cdot c$ as $N$ and $r$ grow. In this work we introduce and analyze algorithms such that asymptotically the distributed storage source data capacity is at least the above equation. Thus, the above equation expresses a fundamental trade-off between network traffic and storage overhead to reliably store source data.

Sanjoy Dasgupta, Michael Luby

We introduce a new model of interactive learning in which an expert examines the predictions of a learner and partially fixes them if they are wrong. Although this kind of feedback is not i.i.d., we show statistical generalization bounds on the quality of the learned model.