Erasure Correction for Graph Codes as a Problem of Bootstrap Percolation

Abstract

Distributed storage systems are designed to have the capability to recover the contents of failed nodes by accessing the contents of other functional nodes in the storage cluster. To achieve this property in storage systems, engineers have focused considerable effort on developing codes that enable local recovery. An encoding method is said to have locality $r$ if the contents of a storage node can be reconstructed by accessing $r$ other nodes in the storage cluster. An additional constraint faced by the designer is accounting for the underlying topology of the system that may affect the functioning of the recovery method. In this research, we study certain aspects of storage systems with graphical structure, modeling them as storage codes on graphs. A storage code is an assignment of bits to the vertices of a graph with the property that every vertex can recover its value from its neighbors. Specializing the problem further, we assume that several vertices in the graph represent failed storage nodes, and the task of code construction is to support their recovery. Suppose that every vertex is erased with some probability $p$ independently from the other vertices, and that the recovery proceeds in rounds, whereby the vertices with more than $r$ functional neighbors are assumed to be able to recover themselves. As the number of erased vertices decreases, additional vertices may be able to restore their values until all the erasures are corrected. In graph-theoretic terms this procedure is known as {\em bootstrap percolation} with infection threshold $r$ (it is often called infection spread in graphs). The research presented in this thesis extends earlier works on bootstrap percolation. We determine asymptotics of the critical probability $p_c$ of bootstrap percolation on the binary $n$-dimensional hypercube, solving for several regimes of dependence of $r$ on the dimension $n$. We also determine the maximum time to erasure recovery (the maximum percolation time) on the $q$-ary hypercube graph. Extending the classical setting, we modify the hypercube graph to expand the neighborhood to allow vertices at distance $2$ or more, and compute the asymptotics of critical probability and obtain other similar asymptotic results.