TY - GEN

T1 - Scalable secure storage when half the system is faulty

AU - Alon, Noga

AU - Kaplan, Haim

AU - Krivelevich, Michael

AU - Malkhi, Dahlia

AU - Stern, Julien

N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 2000.

PY - 2000

Y1 - 2000

N2 - In this paper, we provide a method to safely store a document in perhaps the most challenging settings, a highly decentralized replicated storage system where up to half of the storage servers may incur arbitrary failures, including alterations to data stored in them. Using an error correcting code (ECC), e.g., a Reed-Solomon code, one can take n pieces of a document, replace each piece with another piece of size larger by a factor of n/n−2t such that it is possible to recover the original set even when up to t of the larger pieces are altered. For t close to n/2 the space overhead of this scheme is close to n, and an ECC such as the Reed-Solomon code degenerates to a trivial replication code. We show a technique to reduce this large space overhead for high values of t. Our scheme blows up each piece by a factor slightly larger than two using an erasure code which makes it possible to recover the original set using n/2−O(n/d) of the pieces, where d ≈ 80 is a fixed constant. Then we attach to each piece O(d log n/ log d) additional bits to make it possible to identify a large enough set of unmodified pieces, with negligible error probability, assuming that at least half the pieces are unmodified, and with low complexity. For values of t close to n/2 we achieve a large asymptotic space reduction over the best possible space blowup of any ECC in deterministic setting. Our approach makes use of a d-regular expander graph to compute the bits required for the identification of n/2 − O(n/d) good pieces.

AB - In this paper, we provide a method to safely store a document in perhaps the most challenging settings, a highly decentralized replicated storage system where up to half of the storage servers may incur arbitrary failures, including alterations to data stored in them. Using an error correcting code (ECC), e.g., a Reed-Solomon code, one can take n pieces of a document, replace each piece with another piece of size larger by a factor of n/n−2t such that it is possible to recover the original set even when up to t of the larger pieces are altered. For t close to n/2 the space overhead of this scheme is close to n, and an ECC such as the Reed-Solomon code degenerates to a trivial replication code. We show a technique to reduce this large space overhead for high values of t. Our scheme blows up each piece by a factor slightly larger than two using an erasure code which makes it possible to recover the original set using n/2−O(n/d) of the pieces, where d ≈ 80 is a fixed constant. Then we attach to each piece O(d log n/ log d) additional bits to make it possible to identify a large enough set of unmodified pieces, with negligible error probability, assuming that at least half the pieces are unmodified, and with low complexity. For values of t close to n/2 we achieve a large asymptotic space reduction over the best possible space blowup of any ECC in deterministic setting. Our approach makes use of a d-regular expander graph to compute the bits required for the identification of n/2 − O(n/d) good pieces.

UR - http://www.scopus.com/inward/record.url?scp=37049009792&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=37049009792&partnerID=8YFLogxK

U2 - 10.1007/3-540-45022-x_49

DO - 10.1007/3-540-45022-x_49

M3 - Conference contribution

AN - SCOPUS:37049009792

SN - 9783540450221

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 576

EP - 587

BT - Automata, Languages and Programming - 27th International Colloquium, ICALP 2000, Proceedings

A2 - Montanari, Ugo

A2 - Rolim, Jose D. P.

A2 - Welzl, Emo

PB - Springer Verlag

T2 - 27th International Colloquium on Automata, Languages and Programming, ICALP 2000

Y2 - 9 July 2000 through 15 July 2000

ER -