Abstract
We address the problem of finding the capacity of noisy networks with either independent point-to-point compound channels (CC) or arbitrarily varying channels (AVC). These channels model the presence of a Byzantine adversary, which controls a subset of links or nodes in the network. We derive equivalence results showing that these point-to-point channels with state can be replaced by noiseless bit-pipes without changing the network capacity region. Exact equivalence results are found for the CC model, and for some instances of the AVC, including all nonsymmetrizable AVCs. These results show that a feedback path between the output and input of a CC can increase the equivalent capacity, and that if common randomness can be established between the terminals of an AVC (either by a feedback, a forward path, or via a third-party node), then again the equivalent capacity can increase. This leads to an observation that deleting an edge of arbitrarily small capacity can cause a significant change in network capacity. We also analyze an example involving an AVC for which no fixed-capacity bit-pipe is equivalent.
Original language | English (US) |
---|---|
Article number | 7920294 |
Pages (from-to) | 4137-4154 |
Number of pages | 18 |
Journal | IEEE Transactions on Information Theory |
Volume | 63 |
Issue number | 7 |
DOIs | |
State | Published - Jul 2017 |
All Science Journal Classification (ASJC) codes
- Information Systems
- Computer Science Applications
- Library and Information Sciences
Keywords
- Active adversary
- Arbitrarily-varying channel
- Capacity
- Compound channel
- Equivalence
- Network security