Degree-guided map-reduce task assignment with data locality constraint

Qiaomin Xie, Yi Lu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publication2012 IEEE International Symposium on Information Theory Proceedings, ISIT 2012
Pages985-989
Number of pages5
DOIs
StatePublished - 2012
Event2012 IEEE International Symposium on Information Theory, ISIT 2012 - Cambridge, MA, United States
Duration: Jul 1 2012Jul 6 2012

Publication series

NameIEEE International Symposium on Information Theory - Proceedings

Other

Other2012 IEEE International Symposium on Information Theory, ISIT 2012
CountryUnited States
CityCambridge, MA
Period7/1/127/6/12

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Information Systems
  • Modeling and Simulation
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Degree-guided map-reduce task assignment with data locality constraint'. Together they form a unique fingerprint.

Cite this