TY - GEN
T1 - Degree-guided map-reduce task assignment with data locality constraint
AU - Xie, Qiaomin
AU - Lu, Yi
PY - 2012
Y1 - 2012
N2 - The map-reduce framework is used in many dataintensive parallel processing systems. Data locality is an important problem with map-reduce as tasks with local data complete faster than those with remote data. We propose a degree-guided task assignment algorithm, which uses very little extra information than the currently implemented Random Server algorithm. We analyze a simple version of the degree-guided algorithm, called Peeling algorithm, and the Random Server algorithm in a discrete-time model using evolution of random graphs. We characterize the thresholds below which no queueing takes place and compute the effective service rates for both algorithms. The degree-guided algorithm achieves the optimal performance in the region of practical interest and significantly outperforms the Random Server algorithm. The performance characteristics derived from discrete time model are confirmed with simulation in continuous time.
AB - The map-reduce framework is used in many dataintensive parallel processing systems. Data locality is an important problem with map-reduce as tasks with local data complete faster than those with remote data. We propose a degree-guided task assignment algorithm, which uses very little extra information than the currently implemented Random Server algorithm. We analyze a simple version of the degree-guided algorithm, called Peeling algorithm, and the Random Server algorithm in a discrete-time model using evolution of random graphs. We characterize the thresholds below which no queueing takes place and compute the effective service rates for both algorithms. The degree-guided algorithm achieves the optimal performance in the region of practical interest and significantly outperforms the Random Server algorithm. The performance characteristics derived from discrete time model are confirmed with simulation in continuous time.
UR - http://www.scopus.com/inward/record.url?scp=84867520753&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84867520753&partnerID=8YFLogxK
U2 - 10.1109/ISIT.2012.6284711
DO - 10.1109/ISIT.2012.6284711
M3 - Conference contribution
AN - SCOPUS:84867520753
SN - 9781467325790
T3 - IEEE International Symposium on Information Theory - Proceedings
SP - 985
EP - 989
BT - 2012 IEEE International Symposium on Information Theory Proceedings, ISIT 2012
T2 - 2012 IEEE International Symposium on Information Theory, ISIT 2012
Y2 - 1 July 2012 through 6 July 2012
ER -