A new hybrid coding scheme: homomorphic minimum bandwidth repairing codes

摘要

We propose a new hybrid coding scheme to store data reliably, homomorphic minimum bandwidth repairing (HMBR) codes derived from exact minimum bandwidth regenerating codes (exact-MBR) codes and homomorphic self repairing codes (HSRCs). Exact-MBR codes offer minimum bandwidth usage whereas HSRC has low computational overhead in node repair. Our coding scheme provides two options for node repair operation. The first option offers to repair a node using minimum bandwidth and higher computational complexity while the second one repairs a node using fewer helper nodes, lower computational complexity, lower I/O overhead and higher bandwidth. Our scheme also introduces a basic integrity checking mechanism. Moreover, our proposed codes provide two different data reconstruction methods. The first one has typically better computational complexity while the other requires less bandwidth usage. Our theoretical and experimental results show that the probability of successful node repair in HMBR codes is higher than that of HSRCs and are slightly less than that of exact-MBR codes. Our proposed codes are appropriate for the systems where cost parameters such as computational complexity, bandwidth, the number of helper nodes and I/O can change dynamically. Thus, these systems can choose the appropriate method for node repair as well as the data reconstruction.