Video compression reduces the required bit rate and thereby enables a number of applications such as digital television and video over the Internet. However, compression also makes the video much more susceptible to errors, e.g. bit errors or packet loss. Generally there is a tradeoff between the compression of a signal and the error resilience of the compressed representation. However, recently there have been a number of developments which provide significant improvements in error-resilience while resulting in relatively small reductions in compression. This paper provides an overview of current error-resilient compression methods and also proposes an error-resilient coding scheme referred to as Multiple State Streams (MSS). Conventional video compression standards employ a similar architecture which we refer to as single-state systems since they have a single state (e.g. the previously decoded frame) which if lost or corrupted adversely affects all subsequent frames until the state is reinitialized (the prediction is refreshed). We propose to combat this problem of incorrect state at the decoder with MSS by coding the video into multiple independently decodable streams, each with its own prediction process and state, such that if one stream is lost the other streams can still be used to produce usable video. More importantly, the correctly received streams provide improved error concealment and enable faster state recovery for the lost stream.