On Error Correction for Networks and Deadlines

Classical coding theory deals with the problem of robust transmission on individual unreliable channels. Its network generalization, called network error correction coding, considers coding for networks where some links may be erroneous. Many existing works have studied network error correction coding for single-source multicast networks with uniform link capacities. For the case of multiple sources, multiple receivers with different demands, or nonuniform link capacities, we show that new coding schemes and capacity bounding techniques are required. We further introduce applications beyond the original network communication context.  One application is streaming communication, where specific information must be decoded by specific deadlines.  This can be modeled as a network error/erasure correction problem where each deadline corresponds to a receiver with different demands.  We use this perspective to characterize capacity and design good codes.  In decentralized networks, our results on secure multi-source network error correction can be used for decentralized distribution of information (such as keys from a pool) when not all participating nodes are trustworthy.  We also construct rateless network error correction codes suitable for combining coding-based information theoretic security (which uses path diversity and redundant capacity as resources) with cryptographic security (which relies on computation as a Resource) in networks of computationally limited devices.