  A linear block code with dimension $k$, length $n$, and minimum distance $d$
is called a locally repairable code (LRC) with locality $r$ if it can retrieve
any coded symbol by at most $r$ other coded symbols. LRCs have been recently
proposed and used in practice in distributed storage systems (DSSs) such as
Windows Azure storage and Facebook HDFS-RAID. Theoretical bounds on the maximum
locality of LRCs ($r$) have been established. The \textit{average} locality of
an LRC ($\overline{r}$) directly affects the costly repair bandwidth, disk I/O,
and number of nodes involved in the repair process of a missing data block.
There is a gap in the literature studying $\overline{r}$. In this paper, we
establish a lower bound on $\overline{r}$ of arbitrary $(n,k,d)$ LRCs.
Furthermore, we obtain a tight lower bound on $\overline{r}$ for a practical
case where the code rate $(R=\frac{k}{n})$ is greater than
$(1-\frac{1}{\sqrt{n}})^2$. Finally, we design three classes of LRCs that
achieve the obtained bounds on $\overline{r}$. Comparing with the existing
LRCs, our proposed codes improve the average locality without sacrificing such
crucial parameters as the code rate or minimum distance.
