  Coded distributed computing was recently introduced to mitigate the effect of
stragglers on distributed computing. This paper combines ideas of approximate
computing with coded computing to further accelerate computation. We propose
successive approximation coding (SAC) techniques that realize a tradeoff
between accuracy and speed, allowing the distributed computing system to
produce approximations that increase in accuracy over time. If a sufficient
number of compute nodes finish their tasks, SAC exactly recovers the desired
computation. We theoretically provide design guidelines for our SAC techniques,
and numerically show that SAC achieves a better accuracy-speed tradeoff in
comparison with previous methods.
