  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.
