Characterization of Randomized Shuffle and Sort Quantifiability in MapReduce Model

Quantifiability is a concept in MapReduce Analytics based on the following two conditions: (a) a mapper should be cautious, that is, should not exclude any reducer's shuffle and sort strategy from consideration; and (b) a mapper should respect the reducers' shuffle and sort preferences, that is, should deem a reducer's shuffle and sort strategy k i infinitely more likely than k' i if it premises the reducer to prefer k i to k' i .A shuffle and sort strategy is quantifiable if it can optimally be chosen under common shuffle and sort conjecture in the events (a) and (b).In this paper we present an algorithm that for every finite MapReduce operation computes the set of all quantifiable shuffle and sort strategies.The algorithm is based on the new idea of a key-value preference limitation, which is a pair (k i , V i ) consisting of a shuffle and sort strategy k i , and a subset of shuffle and sort strategies V i , for mapper i.The interpretation is that mapper i prefers some shuffle and sort strategy in V i to k i .The algorithm proceeds by successively adding key-value preference limitations to the MapReduce.