Nonlinear network coding is necessary to combat general Byzantine attacks

Oliver Kosut, Lang Tong, David TseAllerton 2009 · OpenReview

Abstract

We consider the problem of achieving capacity through network coding when some of the nodes act covertly as Byzantine adversaries. For several case-study networks, we investigate rates of reliable communication through network coding and upper bounds on capacity. We show that linear codes are inadequate in general, and a slight augmentation of the class of linear codes can increase throughput. Furthermore, we show that even this nonlinear augmentation may not be enough to achieve capacity. We introduce a new class of codes known as bounded-linear that make use of distributions defined over bounded sets of integers subject to linear constraints using real arithmetic.
BibTeX
@inproceedings{kosut2009nonlinear,
  author = {Oliver Kosut and Lang Tong and David Tse},
  title = {{Nonlinear network coding is necessary to combat general Byzantine attacks}},
  booktitle = {Allerton},
  year = {2009},
  url = {https://openreview.net/forum?id=RAZDWis9gT},
}

Loading related content...

Figure