Adversarial network coding

Alberto Ravagnani, Frank R. Kschischang

Research output: Contribution to journalArticleAcademicpeer-review

3 Citations (Scopus)

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 languageEnglish
Article number8445604
Pages (from-to)198-219
Number of pages22
JournalIEEE Transactions on Information Theory
Volume65
Issue number1
DOIs
Publication statusPublished - Jan 2019
Externally publishedYes

Keywords

  • adversarial models
  • capacity region
  • compound zero-error capacity
  • multi-source networks
  • Network coding
  • one-shot capacity
  • zero-error capacity

Fingerprint

Dive into the research topics of 'Adversarial network coding'. Together they form a unique fingerprint.

Cite this