text: abstract
  owing to data-intensive large-scale applications, distributed computation systems have gained
  significant recent interest, due to their ability of running such tasks over a large number of commodity nodes in a time efficient manner. one of the major bottlenecks that adversely impacts
  the time efficiency is the computational heterogeneity of distributed nodes, often limiting the
  task completion time due to the slowest worker. in this paper, we first present a lower bound
  on the expected computation time based on the work-conservation principle. we then present
  our approach of work exchange to combat the latency problem, in which faster workers can be
  reassigned additional leftover computations that were originally assigned to slower workers. we
  present two variations of the work exchange approach: a) when the computational heterogeneity
  knowledge is known a priori; and b) when heterogeneity is unknown and is estimated in an online
  manner to assign tasks to distributed workers. as a baseline, we also present and analyze the use
  of an optimized maximum distance separable (mds) coded distributed computation scheme
  over heterogeneous nodes. simulation results also compare the proposed approach of work exchange, the baseline mds coded scheme and the lower bound obtained via work-conservation
  principle. we show that the work exchange scheme achieves time for computation which is very
  close to the lower bound with limited coordination and communication overhead even when the
  knowledge about heterogeneity levels is not available.