NDLI: Self-repairing homomorphic codes for distributed storage systems

Content Provider	IEEE Xplore Digital Library
Author	Oggier, F. Datta, A.
Copyright Year	2011
Description	Author affiliation: Division of Mathematical Sciences, School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore (Oggier, F.) \|\| Division of Computer Science, School of Computer Engineering, Nanyang Technological University, Singapore (Datta, A.)
Abstract	Erasure codes provide a storage efficient alternative to replication based redundancy in (networked) storage systems. They however entail high communication overhead for maintenance, when some of the encoded fragments are lost and need to be replenished. Such overheads arise from the fundamental need to recreate (or keep separately) first a copy of the whole object before any individual encoded fragment can be generated and replenished. There has recently been intense interest to explore alternatives, most prominent ones being regenerating codes (RGC) and hierarchical codes (HC). We propose as an alternative a new family of codes to improve the maintenance process, called self-repairing codes (SRC), with the following salient features: (a) encoded fragments can be repaired directly from other subsets of encoded fragments by downloading less data than the size of the complete object, ensuring that (b) a fragment is repaired from a fixed number of encoded fragments, the number depending only on how many encoded blocks are missing and independent of which specific blocks are missing. These properties allow for not only low communication overhead to recreate a missing fragment, but also independent reconstruction of different missing fragments in parallel, possibly in different parts of the network. The fundamental difference between SRCs and HCs is that different encoded fragments in HCs do not have symmetric roles (equal importance). Consequently the number of fragments required to replenish a specific fragment in HCs depends on which specific fragments are missing, and not solely on how many. Likewise, object reconstruction may need different number of fragments depending on which fragments are missing. RGCs apply network coding over (n, k) erasure codes, and provide network information flow based limits on the minimal maintenance overheads. RGCs need to communicate with at least k other nodes to recreate any fragment, and the minimal overhead is achieved if only one fragment is missing, and information is downloaded from all the other n−1 nodes. We analyze the static resilience of SRCs with respect to erasure codes, and observe that SRCs incur marginally larger storage overhead in order to achieve the aforementioned properties. The salient SRC properties naturally translate to low communication overheads for reconstruction of lost fragments, and allow reconstruction with lower latency by facilitating repairs in parallel. These desirable properties make SRC a practical candidate for networked distributed storage systems.
Starting Page	1215
Ending Page	1223
File Size	457362
Page Count	9
File Format	PDF
ISBN	9781424499199
ISSN	0743166X
e-ISBN	9781424499212
DOI	10.1109/INFCOM.2011.5934901
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2011-04-10
Publisher Place	China
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Maintenance engineering Polynomials Encoding Redundancy Peer to peer computing Resilience Decoding self-repair coding networked storage
Content Type	Text
Resource Type	Article
Subject	Computer Science Electrical and Electronic Engineering

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Self-Repairing Codes for distributed storage — A projective geometric construction

Byzantine fault tolerance of regenerating codes

General Fractional Repetition Codes for Distributed Storage Systems

Node recovery schemes for minimizing repair time in distributed storage system with network coding

General self-repairing codes for distributed storage systems

Distributed storage systems and connection to network coding

Homomorphic Self-repairing Codes for Agile Maintenance of Distributed Storage Systems

Analysis and construction of functional regenerating codes with uncoded repair for distributed storage systems

Survivable Distributed Storage with Progressive Decoding

Self-repairing homomorphic codes for distributed storage systems

Similar Documents

Self-Repairing Codes for distributed storage — A projective geometric construction

Byzantine fault tolerance of regenerating codes

General Fractional Repetition Codes for Distributed Storage Systems

Node recovery schemes for minimizing repair time in distributed storage system with network coding

General self-repairing codes for distributed storage systems

Distributed storage systems and connection to network coding

Homomorphic Self-repairing Codes for Agile Maintenance of Distributed Storage Systems

Analysis and construction of functional regenerating codes with uncoded repair for distributed storage systems

Survivable Distributed Storage with Progressive Decoding

Self-repairing homomorphic codes for distributed storage systems