Optimistic Erasure Coded Distributed Storage

Erasure coded storage provides a cheap and space efficient way to tolerate failures through the use of networked commodity servers. Erasure coded data is kept on n different servers out of which f can fail. By combining encoded blocks from n-f servers, the data can be read back. This paper presents ORCAS, an Optimistic eRasure Coded Atomic Storage algorithm. ORCAS is the first wait-free, optimally resilient (n > 2f) erasure coded storage for systems with asynchronous processes that can crash and recover. ORCAS is optimistic in the sense that very little space is used for data written during best case periods which are synchronous and failure-free. During asynchronous periods the storage overhead is higher, but atomicity is still guaranteed. We prove worst case as well as best case bounds on the space complexity of erasure coded storage algorithms. We show that ORCAS matches the asynchronous as well as the synchronous and failure-free bounds. Indirectly, we show that tolerating asynchronous periods does not increase storage overhead during synchronous periods.