132 Large Scale and Big Data
with similar inputs, many tasks are repeated and their results can be reused. To
dene stability more precisely, consider performing MapReduce computations with
inputs I and I′ and consider the respective set of tasks that are executed, denoted
T and T′. We say that a task t ∈ T′ is not matched if t ∉ T, that is, the task that is
performed with input I′ is not performed with the input I. We say that a MapReduce
computation is stable if the time required to execute the unmatched tasks is small,
where small can be more precisely dened as sublinear in the size of the input.
In the case of MapReduce, stability can be affected by several factors, which
we can group into the following two categories: (a) making a sma ...