A Decentralized Algorithm for Erasure-Coded Virtual Disks

Frolund, Svend ; Merchant, Arif ; Saito, Yasushi ; Spence, Susan ; Veitch, Alistair

HP Development Company

关键词: quorum systems;    erasure-coding;    crash-recovery;    storage systems;    distributed systems;   

RP-ID  :  HPL-2004-46

学科分类：计算机科学（综合）

美国|英语

来源: HP Labs

【 摘 要 】

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