  We introduce a new family of Fountain codes that are systematic and also have
sparse parities. Given an input of $k$ symbols, our codes produce an unbounded
number of output symbols, generating each parity independently by linearly
combining a logarithmic number of randomly selected input symbols. The
construction guarantees that for any $\epsilon>0$ accessing a random subset of
$(1+\epsilon)k$ encoded symbols, asymptotically suffices to recover the $k$
input symbols with high probability.
  Our codes have the additional benefit of logarithmic locality: a single lost
symbol can be repaired by accessing a subset of $O(\log k)$ of the remaining
encoded symbols. This is a desired property for distributed storage systems
where symbols are spread over a network of storage nodes. Beyond recovery upon
loss, local reconstruction provides an efficient alternative for reading
symbols that cannot be accessed directly. In our code, a logarithmic number of
disjoint local groups is associated with each systematic symbol, allowing
multiple parallel reads.
  Our main mathematical contribution involves analyzing the rank of sparse
random matrices with specific structure over finite fields. We rely on
establishing that a new family of sparse random bipartite graphs have perfect
matchings with high probability.
