Lossy source coding with Byzantine adversaries

We study a problem in which a source is encoded into n packets, any t of which may be altered in an arbitrary way by Byzantine adversaries. The decoder receives the n packets and, without knowing which packets were altered, seeks to reconstruct the original source to meet a distortion constraint. We examine a layered architecture for this problem that separates the lossy compression from the coding for adversarial errors. We show that this architecture is optimal in the binary-Hamming and quadratic-Gaussian cases yet suboptimal in general. Our optimality proofs use characterizations of the size of a maximal set with a given diameter in Hamming and Euclidean spaces.