License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.OPODIS.2016.28
URN: urn:nbn:de:0030-drops-70970
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7097/
Konwar, Kishori M. ;
Prakash, N. ;
Lynch, Nancy A. ;
Médard, Muriel
RADON: Repairable Atomic Data Object in Networks
Abstract
Erasure codes offer an efficient way to decrease storage and communication costs while implementing atomic memory service in asynchronous distributed storage systems. In this paper, we provide erasure-code-based algorithms having the additional ability to perform background repair of crashed nodes. A repair operation of a node in the crashed state is triggered externally, and is carried out by the concerned node via message exchanges with other active nodes in the system. Upon completion of repair, the node re-enters active state, and resumes participation in ongoing and future read, write, and repair operations. To guarantee liveness and atomicity simultaneously, existing works assume either the presence of nodes with stable storage, or presence of nodes that never crash during the execution. We demand neither of these; instead we consider a natural, yet practical network stability condition N1 that only restricts the number of nodes in the crashed/repair state during broadcast of any message.
We present an erasure-code based algorithm RADON_{C} that is always live, and guarantees atomicity as long as condition N1 holds. In situations when the number of concurrent writes is limited, RADON_{C} has significantly improved storage and communication cost over a replication-based algorithm RADON_{R}, which also works under N1. We further show how a slightly stronger network stability condition N2 can be used to construct algorithms that never violate atomicity. The guarantee of atomicity comes at the expense of having an additional phase during the read and write operations.
BibTeX - Entry
@InProceedings{konwar_et_al:LIPIcs:2017:7097,
author = {Kishori M. Konwar and N. Prakash and Nancy A. Lynch and Muriel M{\'e}dard},
title = {{RADON: Repairable Atomic Data Object in Networks}},
booktitle = {20th International Conference on Principles of Distributed Systems (OPODIS 2016)},
pages = {28:1--28:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-031-6},
ISSN = {1868-8969},
year = {2017},
volume = {70},
editor = {Panagiota Fatourou and Ernesto Jim{\'e}nez and Fernando Pedone},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7097},
URN = {urn:nbn:de:0030-drops-70970},
doi = {10.4230/LIPIcs.OPODIS.2016.28},
annote = {Keywords: Atomicity, repair, fault-tolerance, storage cost, erasure codes}
}
|
Keywords: |
|
Atomicity, repair, fault-tolerance, storage cost, erasure codes |
|
Collection: |
|
20th International Conference on Principles of Distributed Systems (OPODIS 2016) |
|
Issue Date: |
|
2017 |
|
Date of publication: |
|
06.04.2017 |
