Centralized Repair of Multiple Node Failures With Applications to Communication Efficient Secret Sharing

By Ankit Singh Rawat, Onur Ozan Koyluoglu, Sriram Vishwanath. 2016

66 citations recorded by the source corpus.

This paper considers a distributed storage system, where multiple storage nodes can be reconstructed simultaneously at a centralized location. This centralized multi-node repair (CMR) model is a generalization of regenerating codes that allow for bandwidth efficient repair of a single-failed node. This paper focuses on the tradeoff between the amount of data stored and repair bandwidth in the CMR model. In particular, repair bandwidth bounds are derived for the minimum storage multi-node repair (MSMR) and the minimum bandwidth multi-node repair (MBMR) operating points. The tightness of these bounds is analyzed via code constructions. The MSMR point is characterized by codes achieving this point under functional repair for the general set of CMR parameters, as well as with codes enabling exact repair for certain CMR parameters. The MBMR point, on the other hand, is characterized with exact repair codes for all CMR parameters for systems that satisfy a certain entropy accumulation property. Finally, the model proposed here is utilized for the secret sharing problem, where the codes for the multi-node repair problem are used to construct communication efficient secret sharing schemes with the property of bandwidth efficient share repair.

Subfields: Computer Networks and Communications

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

1. Salim el Rouayheb
2. Rawad Bitar
3. Jörg Kliewer
4. Michael Langberg
5. Wentao Huang
6. Jehoshua Bruck

Citations in the corpus

• Staircase-PIR: Universally Robust Private Information Retrieval (2018, background): “In this section, we explore more this connection between communication efficient secret sharing [32]– [34] and capacity achieving robust PIR schemes.”
• Communication Efficient Secret Sharing (2015, background): “There are a number of interesting open problems: 1) in the application of distributed storage, how can one construct codes that are communication efficient in terms of both decoding and repair? We note that very recently, [17], [26] have addressed this problem for certain sets of parameters.”