Abstract
A combinatorial framework for adversarial network coding is presented. Channels are described by specifying the possible actions that one or more (possibly coordinated) adversaries may take. Upper bounds on three notions of capacity - the one-shot capacity, the zero-error capacity, and the compound zero-error capacity - are obtained for point-to-point channels, and generalized to corresponding capacity regions appropriate for multi-source networks. A key result of this paper is a general method by which bounds on these capacities in point-to-point channels may be ported to networks. This technique is illustrated in detail for Hamming-type channels with multiple adversaries operating on specific coordinates, which correspond, in the context of networks, to multiple adversaries acting on specific network edges. Capacity-achieving coding schemes are described for some of the considered adversarial models.
| Original language | English |
|---|---|
| Article number | 8445604 |
| Pages (from-to) | 198-219 |
| Number of pages | 22 |
| Journal | IEEE Transactions on Information Theory |
| Volume | 65 |
| Issue number | 1 |
| DOIs | |
| Publication status | Published - Jan 2019 |
| Externally published | Yes |
Funding
Manuscript received June 12, 2017; revised January 16, 2018, May 28, 2018, and July 12, 2018; accepted July 13, 2018. Date of publication August 24, 2018; date of current version December 19, 2018. This work was supported in part by the Swiss National Science Foundation under Grant P2NEP2_168527. The authors are with the Edward S. Rogers Sr. Department of Electrical & Computer Engineering, University of Toronto, Toronto, ON M5S 3G4, Canada (e-mail: [email protected]; [email protected]). Communicated by P. Sadeghi, Associate Editor for Coding Techniques. Digital Object Identifier 10.1109/TIT.2018.2865936
Keywords
- adversarial models
- capacity region
- compound zero-error capacity
- multi-source networks
- Network coding
- one-shot capacity
- zero-error capacity