  Nowadays, a computing cluster in a typical data center can easily consist of
hundreds of thousands of commodity servers, making component/ machine failures
the norm rather than exception. A parallel processing job can be delayed
substantially as long as one of its many tasks is being assigned to a failing
machine. To tackle this so-called straggler problem, most parallel processing
frameworks such as MapReduce have adopted various strategies under which the
system may speculatively launch additional copies of the same task if its
progress is abnormally slow or simply because extra idling resource is
available. In this paper, we focus on the design of speculative execution
schemes for a parallel processing cluster under different loading conditions.
For the lightly loaded case, we analyze and propose two optimization-based
schemes, namely, the Smart Cloning Algorithm (SCA) which is based on maximizing
the job utility and the Straggler Detection Algorithm (SDA) which minimizes the
overall resource consumption of a job. We also derive the workload threshold
under which SCA or SDA should be used for speculative execution. Our simulation
results show both SCA and SDA can reduce the job flowtime by nearly 60%
comparing to the speculative execution strategy of Microsoft Mantri. For the
heavily loaded case, we propose the Enhanced Speculative Execution (ESE)
algorithm which is an extension of the Microsoft Mantri scheme. We show that
the ESE algorithm can beat the Mantri baseline scheme by 18% in terms of job
flowtime while consuming the same amount of resource.
