A Rate-Optimal Construction of Codes with Sequential Recovery with Low Block Length

An erasure code is said to be a code with sequential recovery with parameters r and t, if for any s ≤ t erased code symbols, there is an s-step recovery process in which at each step we recover exactly one erased code symbol by contacting at most r other code symbols. In this paper, we give a construction of binary codes with sequential recovery that are rate-optimal for any value of t and any value r ≥ 3. Our construction is based on construction of certain kind of tree-like graphs with girth t + 1. We construct these graphs and hence the codes recursively.