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.

TitelProceedings 20th IEEE International Parallel & Distributed Processing Symposium
Herausgeber (Verlag)IEEE
ISBN (Print)1-4244-0054-6
PublikationsstatusVeröffentlicht - 01.01.2006
Veranstaltung20th IEEE International Parallel and Distributed Processing Symposium
- Rhodes Island, Griechenland
Dauer: 25.04.200629.04.2006
Konferenznummer: 114989


Untersuchen Sie die Forschungsthemen von „Construction of Efficient OR-based Deletion-tolerant Coding Schemes“. Zusammen bilden sie einen einzigartigen Fingerprint.