We consider the problem of communicating a message m in the presence of a malicious jamming adversary (Calvin), who can erase an arbitrary set of up to pn bits, out of n transmitted bits X = (x 1 , …, x n ). The capacity of such a channel when Calvin is exactly causal, i.e. Calvin's decision of whether or not to erase bit x i  depends on his observations (x 1 , …, x i ) was recently characterized [1], [2] to be 1 − 2p. In this work we show two (perhaps) surprising phenomena. Firstly, we demonstrate via a novel code construction that if Calvin is delayed by even a single bit, i.e. Calvin's decision of whether or not to erase bit x i  depends only on (x 1 , …, x i−1 ) (and is independent of the “current bit” x i ) then the capacity increases to 1 − p when the encoder is allowed to be stochastic. Secondly, we show via a novel jamming strategy for Calvin that, in the single-bit-delay setting, if the encoding is deterministic (i.e. the transmitted codeword X is a deterministic function of the message m) then no rate asymptotically larger than 1 − 2p is possible with vanishing probability of error, hence stochastic encoding (using private randomness at the encoder) is essential to achieve the capacity of 1− p against a one-bit-delayed Calvin.
['Bikash Kumar Dey', 'Sidharth Jaggi', 'Michael Langberg', 'Anand D. Sarwate']
A bit of delay is sufficient and stochastic encoding is necessary to overcome online adversarial erasures