Locally Recoverable Streaming Codes for Packet-Erasure Recovery

Streaming codes are a class of packet-level erasure codes that are designed with the goal of ensuring recovery in low-latency fashion, of erased packets over a communication network. It is well-known in the streaming code literature, that diagonally embedding codewords of a \([\tau+1,\tau+1-a]\) Maximum Distance Separable (MDS) code within the packet stream, leads to rate-optimal streaming codes capable of recovering from \(a\) arbitrary packet erasures, under a strict decoding delay constraint \(\tau\). Thus MDS codes are geared towards the efficient handling of the worst-case scenario corresponding to the occurrence of \(a\) erasures. In the present paper, we have an increased focus on the efficient handling of the most-frequent erasure patterns. We study streaming codes which in addition to recovering from \(a>1\) arbitrary packet erasures under a decoding delay \(\tau\), have the ability to handle the more common occurrence of a single-packet erasure, while incurring smaller delay \(r<\tau\). We term these codes as \((a, \tau, r)\) locally recoverable streaming codes (LRSCs), since our single-erasure recovery requirement is similar to the requirement of locality in a coded distributed storage system. We characterize the maximum possible rate of an LRSC by presenting rate-optimal constructions for all possible parameters \(\{a, \tau, r\}\). Although the rate-optimal LRSC construction provided in this paper requires large field size, the construction is explicit. It is also shown that our \((a, \tau=a(r+1)-1, r)\) LRSC construction provides the additional guarantee of recovery from the erasure of \(h, 1 \leq h \leq a,\) packets, with delay \(h(r+1)-1\). The construction thus offers graceful degradation in decoding delay with increasing number of erasures.