Modern data centers have been providing exponentially increasing computing and storage resources, which have been fueling core applications ranging from search engines in the early 2000's to the real-time, large-scale data analysis of today. All these breakthroughs were made possible only due to the scalability in computing and storage resources offered by modern large-scale clusters, comprising individually small and unreliable low-end devices. Given the individually unpredictable nature of the underlying devices in these systems, we face the constant challenge of securing predictable and high-quality performance of such systems in the face of uncertainty.

In this thesis, distributed storage and computing systems are viewed through a coding-theoretic lens. The role of codes in providing resiliency against noise has been studied for decades in many other engineering contexts, especially in communication systems, and codes are parts of our everyday infrastructure such as smartphones, WiFi, cellular systems, etc. Since the performance of distributed systems is significantly affected by anomalous system behavior and bottlenecks, which we call "system noise", there is an exciting opportunity for codes to endow distributed systems with robustness against such system noise.

Our key observation – channel noise in communication systems is equivalent to system noise in distributed systems – forms the key motivation of this thesis, and raises the fundamental question: "can we use codes to guarantee robust speedups in distributed storage and computing systems?". In this thesis, three main layers of distributed computing and storage systems – storage layer, computation layer, and communication layer – are robustified through coding-theoretic tools. For the storage layer, we show that coded distributed storage systems allow faster data retrieval in addition to the other known advantages such as higher data durability and lower storage overhead; for the computation layer, we inject computing redundancy into distributed algorithms that are robust to stragglers or nodes that are substantially slower than the other nodes; for the communication layer, we propose a novel data caching and communication protocol, based on coding-theoretic principles that can significantly reduce the network overhead of the data shuffling operation, which is necessary to achieve higher statistical efficiency when running parallel/distributed machine learning algorithms.

Depth data acquisition has drawn considerable interest in recent years as a result of the rapid development of 3D technology. A large number of acquisition techniques are based on hardware devices, e.g., infra-red sensors, time-of-flight camera, and LiDAR, etc, whereas they have limited performance due to poor depth precision and low resolution. In some situations computational methods are preferred due to its flexibility and low cost. These computational techniques, typically known as depth estimation algorithms, estimate depth maps (in terms of disparities) from a pair of stereo images. However, existing computational techniques are sensitive to various factors such as noise, camera alignment, and illumination, resulting that a few samples are reliable. Therefore, dense depth data reconstruction from sparse samples is a significant technological challenge.

In this thesis, we mainly consider the problem of dense depth data reconstruction from a subset of samples. We present computationally efficient methods to estimate dense depth maps from sparse measurements, and we further extend the work to dense depth video estimation. Working on single depth image, we have three main contributions: First, we provide empirical evidence that depth maps can be encoded much more sparsely than natural images by using common dictionaries such as wavelets and contourlets, and show that disparity maps can be sparsely represented by a combined wavelet and contourlet dictionary. Second, we propose a subgradient algorithm for dense depth image reconstruction, and propose an alternating direction methods of multipliers (ADMM) algorithm with a multi-scale warm start procedure to further speed up the convergence. Third, we propose a two-stage randomized sampling scheme to optimally choose the sampling locations, thus maximizing the reconstruction performance for a given sampling budget. Experimental results show that the proposed methods produce high quality dense depth estimates, and are robust to noisy measurements.

For dealing with depth video sequences, a framework for depth video reconstruction from a subset of samples is proposed. By redefining classical dense depth estimation into two individual problems, sensing and synthesis, we propose a motion compensation assisted sampling (MCAS) scheme and a spatio-temporal depth reconstruction (STDR) algorithm for reconstructing depth video sequences from a subset of samples. Using the 3-dimensional extensible dictionary, 3D-DWT, and applying alternating direction method of multiplier technique, the proposed STDR algorithm possesses scability for temporal volume and efficiency for processing large scale depth data. Exploiting the temporal information and corresponding RGB images, the proposed MCAS scheme achieves an efficient 1-Stage sampling. Experimental results show that the proposed depth reconstruction framework outperforms the existing methods and is competitive comparing to our previous work on sampling single depth image, which requires a pilot signal in the 2-Stage sampling scheme. Finally, to estimate missing reliable depth samples from varying input sources, we present an inference approach using geometrical and color similarities. Applications for depth video super resolution from uniform-grid subsampled data and dense disparity video estimation from a subset of reliable samples are presented.