Construction of Efficient OR-based Deletion-tolerant Coding Schemes

Peter Sobe, Kathrin Peter


Fault-tolerant data layouts for storage systems are based on the principle to add redundancy to groups of data blocks and store them in different fault regions. Commonly, XOR-based codes are used with an optimal redundancy overhead but with the disadvantage of relatively high calculation costs. We present a scheme that encodes input data in a highly redundant code and exploits that redundancy for a fault tolerance scheme. It allows to recalculate missed bits in fewer steps than needed for XOR-based schemes. This simple and efficient en- and decoding requires an appropriate hardware architecture or a highly parallel microprocessor architecture. Particularly, disjunctions over many input bits must be calculated, e.g. by wide OR-gates or busses that are driven by multiple logic input lines. The high redundant encoding is combined with data compression for separated data streams, each stream dedicated to a storage device. The compression not only eliminates the introduced redundancy of the used code, it also eliminates redundancy in the input data.

Original languageEnglish
Title of host publicationProceedings 20th IEEE International Parallel & Distributed Processing Symposium
Publication date01.01.2006
Article number1639663
ISBN (Print)1-4244-0054-6
Publication statusPublished - 01.01.2006
Event20th IEEE International Parallel and Distributed Processing Symposium
- Rhodes Island, Greece
Duration: 25.04.200629.04.2006
Conference number: 114989


Dive into the research topics of 'Construction of Efficient OR-based Deletion-tolerant Coding Schemes'. Together they form a unique fingerprint.

Cite this