  Dealing with the shear size and complexity of today's massive data sets
requires computational platforms that can analyze data in a parallelized and
distributed fashion. A major bottleneck that arises in such modern distributed
computing environments is that some of the worker nodes may run slow. These
nodes a.k.a.~stragglers can significantly slow down computation as the slowest
node may dictate the overall computational time. A recent computational
framework, called encoded optimization, creates redundancy in the data to
mitigate the effect of stragglers. In this paper we develop novel mathematical
understanding for this framework demonstrating its effectiveness in much
broader settings than was previously understood. We also analyze the
convergence behavior of iterative encoded optimization algorithms, allowing us
to characterize fundamental trade-offs between convergence rate, size of data
set, accuracy, computational load (or data redundancy), and straggler
toleration in this framework.
