CaltechAUTHORS
  A Caltech Library Service

Correction of adversarial errors in networks

Jaggi, Siddarth and Langberg, Michael and Ho, Tracey and Effros, Michelle (2005) Correction of adversarial errors in networks. In: International Symposium on Information Theory (ISIT 2005), Adelaide, South Australia, Australia, 4-9 September 2005. IEEE , pp. 1455-1459. ISBN 0-7803-9151-9 http://resolver.caltech.edu/CaltechAUTHORS:JAGisit05

[img]
Preview
PDF
See Usage Policy.

239Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:JAGisit05

Abstract

We design codes to transmit information over a network, some subset of which is controlled by a malicious adversary. The computationally unbounded, hidden adversary knows the message to be transmitted, and can observe and change information over the part of the network he controls. The network nodes do not share resources such as shared randomness or a private key. We first consider a unicast problem in a network with |E| parallel, unit-capacity, directed edges. The rate-region has two parts. If the adversary controls a fraction p < 0.5 of the |E| edges, the maximal throughput equals (1 − p)|E|. We describe low-complexity codes that achieve this rate-region. We then extend these results to investigate more general multicast problems in directed, acyclic networks.


Item Type:Book Section
Additional Information:© Copyright 2005 IEEE. Reprinted with permission. The authors were partially supported by NSF Grants CCR-0325324, CCR-0325673 and CCF-0346991 and a grant from the Lee Center for Advanced Networking at Caltech. We thank Yuval Ishai for pointing out the connection between our results and the known results on VSS.
Record Number:CaltechAUTHORS:JAGisit05
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:JAGisit05
Alternative URL:http://dx.doi.org/10.1109/ISIT.2005.1523584
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:7300
Collection:CaltechAUTHORS
Deposited By: Archive Administrator
Deposited On:26 Jan 2007
Last Modified:26 Dec 2012 09:30

Repository Staff Only: item control page