The problem of communication and computation in the presence of errors
is difficult, and general solutions can be time consuming and inflexi
ble (particularly when implemented with a prescribed error detection/c
orrection). A reasonable approach is to investigate reliable communica
tion in carefully selected areas of fundamental interest where specifi
c solutions may be more practical than general purpose techniques. In
this paper, we study the problem of error-resilient communication and
computation in a particularly challenging area, adaptive lossless data
compression, where the devastating effect of error propagation is a l
ong-standing open problem that was posed in the papers of Lempel and Z
iv in the late 1970s. In fact, the non-error resilience of adaptive da
ta compression has been a practical drawback of its use in many applic
ations. Protocols that require the receiver to request retransmission
from the sender when an error is detected can be impractical for many
applications where such two-way communication is not possible or is se
lf-defeating (e.g., with data compression, retransmission may be tanta
mount to losing the data that could have been transmitted in the mean
time). In addition, bits of encoded data that are corrupted while data
is in storage will in general not be recoverable and may corrupt the
entire decompressed file. By error resilience, we mean that even thoug
h errors may not be detected, there are strong guarantees that their e
ffects will not propagate. Our main result is a provable error-resilie
nt adaptive lossless data-compression algorithm which nevertheless mai
ntains optimal compression over the usual input distributions (e.g., s
tationary ergodic sources). We state our result in the context of a mo
re general model that we call dynamic dictionary communication, where
a sender and receiver work in a ''lock-step'' cooperation to maintain
identical copies of a dictionary D that is constantly changing. For lo
ssless data compression, the dictionary stores a set of strings that h
ave been seen in the past; and data is compressed by sending only indi
ces of strings over the channel. Other applications of our model inclu
de robotics (e.g., remote terrain mapping) and computational learning
theory.