Publication

Optimistic Erasure Coded Distributed Storage

Rachid Guerraoui, Partha Dutta
2008
Reports

Résumé

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.

Source officielle

https://infoscience.epfl.ch/entities/publication/462c343f-5d7b-450a-bdbb-f065a20a067c

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Graph Chat

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

Rachid Guerraoui, Partha Dutta
2008
Reports

Résumé

Source officielle

https://infoscience.epfl.ch/entities/publication/462c343f-5d7b-450a-bdbb-f065a20a067c

À propos de ce résultat

Concepts associés (32)

Code d'effacement

En théorie de l'information, un code d'effacement est un code de correction d'erreur directe pour le canal binaire d'effacement qui transforme un message composé de symboles en un message plus long composé de symboles tel que le message original peut être retrouvé à partir d'un sous-ensemble de ces symboles. La fraction est appelé « débit du code ». La fraction , où représente le nombre de symboles requis pour restaurer le message est appelée efficacité de la réception.

Error correction code

In computing, telecommunication, information theory, and coding theory, forward error correction (FEC) or channel coding is a technique used for controlling errors in data transmission over unreliable or noisy communication channels. The central idea is that the sender encodes the message in a redundant way, most often by using an error correction code or error correcting code (ECC). The redundancy allows the receiver not only to detect errors that may occur anywhere in the message, but often to correct a limited number of errors.

Fountain code

In coding theory, fountain codes (also known as rateless erasure codes) are a class of erasure codes with the property that a potentially limitless sequence of encoding symbols can be generated from a given set of source symbols such that the original source symbols can ideally be recovered from any subset of the encoding symbols of size equal to or only slightly larger than the number of source symbols. The term fountain or rateless refers to the fact that these codes do not exhibit a fixed code rate.

Afficher plus

Publications associées (30)

Afficher plus

Optimistic Erasure Coded Distributed Storage

Chattez avec Graph Search

EPFL Library Research Data Management Fastguides

Data-Driven Transport Geometry for Rare Events in Metastable Systems

Compilation of flume experiments on contraction scour