Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published February 2011 | public
Journal Article

Multiple-Access Network Information-Flow and Correction Codes

Abstract

This work considers the multiple-access multicast error-correction scenario over a packetized network with z malicious edge adversaries. The network has min-cut m and packets of length l, and each sink demands all information from the set of sources S. The capacity region is characterized for both a "side-channel" model (where sources and sinks share some random bits that are secret from the adversary) and an "omniscient" adversarial model (where no limitations on the adversary's knowledge are assumed). In the "side-channel" adversarial model, the use of a secret channel allows higher rates to be achieved compared to the "omniscient" adversarial model, and a polynomial-complexity capacity-achieving code is provided. For the "omniscient" adversarial model, two capacity-achieving constructions are given: the first is based on random subspace code design and has complexity exponential in lm, while the second uses a novel multiple-field-extension technique and has O(lm(|S|) complexity, which is polynomial in the network size. Our code constructions are "end-to-end" in that all nodes except the sources and sinks are oblivious to the adversaries and may simply implement predesigned linear network codes (random or otherwise). Also, the sources act independently without knowledge of the data from other sources.

Additional Information

© 2011 IEEE. Manuscript received April 18, 2010; revised August 03, 2010; accepted September 24, 2010. Date of current version January 19, 2011. The work of T.K. Dikaliotis, S. Vyetrenko, T. Ho, M. Effros, and E. Erez was supported by BAE Systems National Security Solutions, Inc. under subcontract #069153 and by the Defense Advanced Research Projects Agency (DARPA) and the Space and Naval Warfare System Center (SPAWARSYSCEN), San Diego, CA, under Contract N66001-08-C-2013, AFOSR under Grant 5710001972, Caltech's Lee Center for Advanced Networking, and NSF Grant CNS-0905615. The work of S. Jaggi was supported by the RGC GRF Grants 412608 and 412809, the CUHK MoE-Microsoft Key Laboratory of Human-centric Computing and Interface Technologies, the Institute of Theoretical Computer Science and Communications, and Project No. AoE/E-02/08 from the University Grants Committee of the Hong Kong Special Administrative Region, China. The work of H. Yao was supported by the National Natural Science Foundation of China Grant 61033001 and 61073174, the National Basic Research Program of China Grant 2007CB807900 and 2007CB807901, the Hi-Tech research and Development Program of China Grant 2006AA10Z216. The work of J. Kliewer was supported by NSF Grant CCF-0830666. The first five authors, T. K. Dikaliotis, T. Ho, S. Jaggi, S. Vyetrenko, and H. Yao had equal contribution to this work and they are named in alphabetical order. The material in this paper was presented (in part) at the 2009 IEEE International Symposium on Information Theory, Seoul, South Korea, July 2009, and at ITW 2010, Dublin, Ireland, Aug./Sep. 2010. This paper is part of the special issue on "Facets of Coding Theory: From Algorithms to Networks," dedicated to the scientific legacy of Ralf Koetter.

Additional details

Created:
August 22, 2023
Modified:
October 23, 2023