Functional broadcast repair of multiple partial failures in wireless distributed storage systems
File(s)MKLG_JSAIT21.pdf (438.93 KB)
Accepted version
Author(s)
Mital, Nitish
Kralevska, Katina
Ling, Cong
Gunduz, Deniz
Type
Journal Article
Abstract
We consider a distributed storage system with n nodes, where a user can recover the stored file from any k nodes, and study the problem of repairing r partially failed nodes. We consider broadcast repair , that is, d surviving nodes transmit broadcast messages on an error-free wireless channel to the r nodes being repaired, which are then used, together with the surviving data in the local memories of the failed nodes, to recover the lost content. First, we derive the trade-off between the storage capacity and the repair bandwidth for partial repair of multiple failed nodes, based on the cut-set bound for information flow graphs. It is shown that utilizing the broadcast nature of the wireless medium and the surviving contents at the partially failed nodes reduces the repair bandwidth per node significantly. Then, we list a set of invariant conditions that are sufficient for a functional repair code to be feasible. We further propose a scheme for functional repair of multiple failed nodes that satisfies the invariant conditions with high probability, and its extension to the repair of partial failures. The performance of the proposed scheme meets the cut-set bound on all the points on the trade-off curve for all admissible parameters when k is divisible by r , while employing linear subpacketization, which is an important practical consideration in the design of distributed storage codes. Unlike random linear codes, which are conventionally used for functional repair of failed nodes, the proposed repair scheme has lower overhead, lower input-output cost, and lower computational complexity during repair.
Date Issued
2021-12
Date Acceptance
2021-11-03
Citation
IEEE Journal on Selected Areas in Information Theory, 2021, 2 (4), pp.1093-1107
ISSN
2641-8770
Publisher
Institute of Electrical and Electronics Engineers
Start Page
1093
End Page
1107
Journal / Book Title
IEEE Journal on Selected Areas in Information Theory
Volume
2
Issue
4
Copyright Statement
Copyright © 2021 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.
Identifier
https://ieeexplore.ieee.org/document/9608961
Publication Status
Published
Date Publish Online
2021-11-09