  Cloud providers have recently introduced new offerings whereby spare
computing resources are accessible at discounts compared to on-demand
computing. Exploiting such opportunity is challenging inasmuch as such
resources are accessed with low-priority and therefore can elastically leave
(through preemption) and join the computation at any time. In this paper, we
design a new technique called coded elastic computing, enabling distributed
computations over elastic resources. The proposed technique allows machines to
leave the computation without sacrificing the algorithm-level performance, and,
at the same time, adaptively reduce the workload at existing machines when new
ones join the computation. Leveraging coded redundancy, our approach can
achieve similar computational cost as the original (noiseless) method when all
machines are present; the cost gracefully increases when machines are preempted
and reduces when machines join. The performance of the proposed technique is
evaluated on matrix-vector multiplication and linear regression tasks. In
experimental validations, it can achieve exactly the same numerical result as
the noiseless computation, while reducing the computation time by 46% when
compared to non-adaptive coding schemes.
