Click here for full text:
A Decentralized Algorithm for Erasure-Coded Virtual Disks
Frolund, Svend; Merchant, Arif; Saito, Yasushi; Spence, Susan; Veitch, Alistair
HPL-2004-46
Keyword(s): quorum systems; erasure-coding; crash-recovery; storage systems; distributed systems
Abstract: A Federated Array of Bricks is a scalable distributed storage system composed from inexpensive storage bricks. It achieves high reliability with low cost by using erasure coding across the bricks to maintain data reliability in the face of brick failures. Erasure coding generates n encoded blocks from m data blocks (n > m) and permits the data blocks to be reconstructed from any m of these encoded blocks. We present a new fully decentralized erasure-coding algorithm for an asynchronous distributed system. Our algorithm provides fully linearizable read-write access to erasure-coded data and supports concurrent I/O controllers that may crash and recover. Our algorithm relies on a novel quorum construction where any two quorums intersect in m processes. Notes: Copyright IEEE To be published in and presented at the International Conference on Dependable Systems and Networks, 28 June-1 July, 2004, Florence, Italy
19 Pages
Back to Index
| 
Printable version
