Minimizing Tardiness for Data-Intensive Applications in Heterogeneous Systems: A Matching Theory Perspective

Ke Xu, Liang Lv, Tong Li, Meng Shen, Haiyang Wang, Kun Yang

Research output: Contribution to journalArticlepeer-review

14 Scopus citations


The increasing data requirements of Internet applications have driven a dramatic surge in developing new programming paradigms and complex scheduling algorithms to handle data-intensive workloads. Due to the expanding volume and the variety of such flows, their raw data are often processed on Intermediate Processing Nodes (IPNs) before being sent to servers. However, the intermediate processing constraint is rarely considered in existing flow computing models. This paper aims to minimize the tardiness of data-intensive applications in the presence of intermediate processing constraint. Motivating cases show that the tardiness is affected by both IPN locations and flow dispatching strategies. Based on the observation that dispatching flows to IPNs is essentially building a matching between flows and IPNs, a novel solution is proposed based on matching theory. In the deployment phase, a tardiness-aware deferred acceptance algorithm is developed to optimize IPN locations. In the operation phase, the Power-of-D paradigm and matching theory are combined together to dispatch flows efficiently. Evaluation results show that our solution effectively minimizes the total tardiness of data-intensive applications in heterogeneous systems.

Original languageEnglish (US)
Article number8772187
Pages (from-to)144-158
Number of pages15
JournalIEEE Transactions on Parallel and Distributed Systems
Issue number1
StatePublished - Jan 1 2020

Bibliographical note

Publisher Copyright:
© 1990-2012 IEEE.


  • Heterogeneous system
  • data-intensive application
  • matching theory
  • power-of-D


Dive into the research topics of 'Minimizing Tardiness for Data-Intensive Applications in Heterogeneous Systems: A Matching Theory Perspective'. Together they form a unique fingerprint.

Cite this