Event
Ph.D. Research Proposal Exam: Fengxing Zhu
Wednesday, July 19, 2023
2:00 p.m.
AVW 2460
Maria Hoo
301 405 3681
mch@umd.edu
ANNOUNCEMENT: Ph.D. Research Proposal Exam
Name: Fengxing Zhu
Committee:
Professor Alexander Barg (Chair)
Professor Prakash Narayan
Professor Behtash Babadi
Date/time: Wednesday, July 19th, 2023 at 2pm
Location: AVW 2460
Title: Erasure correction as a bootstrap percolation problem
Abstract:
Good distributed storage systems are expected to have the capability to recover the contents of failed nodes by accessing the contents of other functional nodes. To design storage systems with this property, there has been significant attention given to the study of codes with locality. We say $\mathcal{C}$ is a code with locality $r$ if for every codeword $\mathbf c$ and every coordinate $i,$ the value $c_i$ can be recovered by accessing some other $r$ coordinates of $\mathbf{c}$. However, the construction of codes with locality often neglects the underlying topology of the distributed storage systems. 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 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 recovery threshold $r$ (it is often called infection spread in graphs).
Our completed results extend earlier works on bootstrap percolation. We determine asymptotics of the critical probability $p_c$ of bootstrap percolation on the hypercube with $n$ vertices, computing the first term for correction threshold $r=n^a$ with $\frac{2}{3}< a
For future work, we plan to extend the results obtained for the binary hypercube to the $q$-ary case with general $q\ge 2$. We also plan to determine the critical probability of bootstrap percolation on regular graphs with expansion property, addressing a conjecture stated in earlier literature. Overall, these results provide insights into constructions of codes in graph-constrained storage systems.
