Seventh Pacific Rim International Symposium on Dependable Computing (PRDC'00)
Transient errors and rollback recovery in LZ compression
Los Angeles, California
December 18-December 20
ISBN: 0-7695-0975-4
This paper analyzes the data integrity of one of the most widely used lossless data compression techniques, Lempel-Ziv (LZ) compression. In this algorithm, because the data reconstruction from compressed codewords relies on previously decoded results, a transient error during compression may propagate to the decoder and cause a significant corruption in the reconstructed data. To recover the system from transient faults, we designed two rollback error recovery schemes for the LZ compression hardware, the "reload-retry" and "direct-retry" schemes. Statistical analyses show that the "reload-retry" scheme can recover the LZ compression process from transient faults in one dictionary reload cycle with a small amount of hardware redundancy. The "direct-retry" scheme can recover normal operations with a shorter latency but with a small degradation in the compression ratio.
Index Terms:
data integrity; data compression; system recovery; error detection; fault tolerant computing; transient errors; rollback recovery; LZ compression; data integrity; lossless data compression; Lempel-Ziv compression; data reconstruction; compressed codewords; transient faults; rollback error recovery schemes; hardware redundancy; compression ratio
Citation:
Wei-Je Huang, E.J. McCluskey, "Transient errors and rollback recovery in LZ compression," prdc, pp.128, Seventh Pacific Rim International Symposium on Dependable Computing (PRDC'00), 2000