In a distributed storage system (DSS), data is required to be stored reliably and efficiently across nodes in a network, where the nodes themselves are failure-prone. Metrics of interest in a distributed storage system are (i) Storage overhead (ii) Reliability (iii) Number of nodes contacted for the repair of a failed node termed the repair degree (iv) Total amount of data downloaded to repair a failed node termed repair bandwidth. It is of interest to have, with a certain degree of reliability, low storage overhead, low repair degree and low repair bandwidth. DSS found in practice, include Windows Azure Storage and the Hadoop-based systems used in Facebook and Yahoo. Replication is mostly commonly employed in DSS. However, the storage overhead incurred by replication is very high and turns out to be an expensive option for the exponentially increasing volume of data. Maximum-distance separable (MDS) codes are also used in distributed storage systems, for example in HDFS RAID. MDS coding schemes, while optimal in terms of storage overhead, are however inefficient in terms of node repair, as the repair degree as well as repair bandwidth are both large. Two alternative approaches to coding have recently been advocated in literature to enable more efficient node repair, namely, regenerating codes and codes with locality. In a situation where one is attempting to repair a failed node, regenerating codes seek to minimize the amount of data downloaded for node repair, while codes with locality attempt to minimize the number of helper nodes accessed. We extend these results in two directions.

To handle multiple erasures, we consider two approaches. In the first approach, we consider the framework where code symbols are covered using stronger local codes. This framework enables parallel (local) recovery of erasures. In the second approach, we consider codes with locality via sequential recovery for the case of two erasures. In both the approaches, we present bounds on minimum distance and optimal constructions.

The second direction seeks to build codes that combine the advantages of both codes with locality as well as regenerating codes. These codes, termed here as codes with local regeneration, are codes with locality over a vector alphabet, in which the local codes themselves are regenerating codes. We derive an upper bound on the minimum distance of a class of vector-alphabet codes with locality and provide several constructions of codes with local regeneration which achieve this bound.The constructions include both the cases where the locally regenerating codes correspond to the MSR as well as the MBR point on the storage-repair-bandwidth tradeoff curve of regenerating codes.

We evaluate the efficacy of two specific coding solutions, both possessing an inherent double replication of data, in a practical distributed storage setting known as Hadoop. Hadoop is an open-source platform dealing with distributed storage of data in which the primary aim is to perform distributed computation on the stored data via a paradigm known as MapReduce. We observe that under the current architecture, the choice of the number of processor cores per node and map-task scheduling algorithm play a major role in determining their performance.

This problem is motivated by the problem of distributed function computation considered by Korner and Marton, where the goal is to compute XOR of two binary sources at the receiver. It has been shown that linear encoders give better sum rates for some source distributions as compared to the usual Slepian-Wolf scheme. We generalize this distributed function computation setting to the case of more than two sources and the receiver is interested in computing multiple linear combinations of the sources. Consider ‘$m$’ random variables each of which takes values from a finite field and are associated with a certain joint probability distribution. The receiver is interested in the lossless computation of ‘$s$’ linear combinations of the $m$ random variables. By considering the set of all linear combinations of $m$ random variables as a vector space $V$, this problem can be interpreted as a subspace-computation problem. For this problem, we develop two approaches, both based on linear encoders. The first approach uses a common matrix to encode all the sources and the second one uses nested codes. In both the approaches, at the receiver, potentially more linear combinations than those required are decoded. The superset of linear combinations which has to be decoded at the receiver is identified through a subspace chain decomposition based on joint distribution of the 'm’ random variables and a notion of normalized measure of entropy.

If the source $X$ is drawn from a Galois field, we know from information theory that the source can be compressed to its entropy, $H(X)$ bits. The entropy, roughly speaking, is the amount of information that the source possesses. Moreover, such compression can be carried out using linear maps i.e., using matrices over the finite field. Now, consider the case when the alphabet is the Galois ring $Z_{p^r}$, the ring of integers modulo $p^r$, $p$ a prime and $r >1$. While information theory says that this source can be compressed to its entropy, unlike in the case of Galois fields such compression is not always possible by using linear maps. We show that the presence of non-trivial ideals in these rings is the cause for the sub-optimality of linear compression.