Equivalence for networks with adversarial state

Oliver Kosut, Jörg Kliewer

Research output: Contribution to journalArticlepeer-review

4 Scopus citations


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 languageEnglish (US)
Article number7920294
Pages (from-to)4137-4154
Number of pages18
JournalIEEE Transactions on Information Theory
Issue number7
StatePublished - Jul 2017

All Science Journal Classification (ASJC) codes

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences


  • Active adversary
  • Arbitrarily-varying channel
  • Capacity
  • Compound channel
  • Equivalence
  • Network security


Dive into the research topics of 'Equivalence for networks with adversarial state'. Together they form a unique fingerprint.

Cite this