Event
Ph.D. Dissertation Defense: Fengxing Zhu
Monday, June 9, 2025
2:00 p.m.
AVW 1146
Maria Hoo
301 405 3681
mch@umd.edu
ANNOUNCEMENT: Ph.D. Dissertation Defense
Name: Fengxing Zhu
Committee:
Professor Alexander Barg (Chair)
Professor Behtash Babadi
Professor Armand M. Makowski
Professor Prakash Narayan
Professor Aravind Srinivasan (Dean's Representative)
Date/time: Monday, June 9th, 2025 at 2pm
Location: AVW 1146
Title: 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.
