Distributed workflow mapping algorithm for maximized reliability under end-to-end delay constraint

Fei Cao, Michelle Zhu

Research output: Contribution to journalArticleResearchpeer-review

4 Citations (Scopus)

Abstract

A distributed scientific workflow mapping algorithm for maximized reliability under certain end-to-end delay (EED) bound is proposed. It is studied in a heterogeneous distributed computing environment, where computing node and communication link failures are inevitable. The mapping decision and the stored table information is distributed among various nodes in order to achieve scalability and robustness, which are especially important for large-scale distributed systems. This Distributed Reliability Maximization workflow mapping algorithm under End-to-end Delay constraint (dis-DRMED) considers both the maximum reliability and the minimum EED objectives in a two-step procedure. In the first step, a mapping algorithm combining iterative Critical Path search and Layer-based priority assigning techniques (CPL) is adopted to minimize the EED by focusing on the optimal allocation of tasks on the critical path. In the second step, tasks on noncritical paths are remapped to improve the overall execution reliability. Simulation results under various system setups demonstrated that dis-DRMED achieved considerably higher reliability values under the same EED constraint compared with some representative workflow mapping algorithms.

Original languageEnglish
Pages (from-to)1462-1488
Number of pages27
JournalJournal of Supercomputing
Volume66
Issue number3
DOIs
StatePublished - 22 Apr 2013

Fingerprint

End-to-end Delay
Work Flow
Critical Path
Scientific Workflow
Heterogeneous Computing
Distributed computer systems
Optimal Allocation
Large-scale Systems
Vertex of a graph
Distributed Computing
Telecommunication links
Scalability
Distributed Systems
Table
Robustness
Minimise
Path
Computing
Simulation

Keywords

  • Distributed computing
  • Maximized reliability
  • Minimum end-to-end delay
  • Workflow mapping

Cite this

@article{22a5f07e0e1140cbb0032793e91c98b3,
title = "Distributed workflow mapping algorithm for maximized reliability under end-to-end delay constraint",
abstract = "A distributed scientific workflow mapping algorithm for maximized reliability under certain end-to-end delay (EED) bound is proposed. It is studied in a heterogeneous distributed computing environment, where computing node and communication link failures are inevitable. The mapping decision and the stored table information is distributed among various nodes in order to achieve scalability and robustness, which are especially important for large-scale distributed systems. This Distributed Reliability Maximization workflow mapping algorithm under End-to-end Delay constraint (dis-DRMED) considers both the maximum reliability and the minimum EED objectives in a two-step procedure. In the first step, a mapping algorithm combining iterative Critical Path search and Layer-based priority assigning techniques (CPL) is adopted to minimize the EED by focusing on the optimal allocation of tasks on the critical path. In the second step, tasks on noncritical paths are remapped to improve the overall execution reliability. Simulation results under various system setups demonstrated that dis-DRMED achieved considerably higher reliability values under the same EED constraint compared with some representative workflow mapping algorithms.",
keywords = "Distributed computing, Maximized reliability, Minimum end-to-end delay, Workflow mapping",
author = "Fei Cao and Michelle Zhu",
year = "2013",
month = "4",
day = "22",
doi = "10.1007/s11227-013-0938-3",
language = "English",
volume = "66",
pages = "1462--1488",
journal = "Journal of Supercomputing",
issn = "0920-8542",
publisher = "Springer Netherlands",
number = "3",

}

Distributed workflow mapping algorithm for maximized reliability under end-to-end delay constraint. / Cao, Fei; Zhu, Michelle.

In: Journal of Supercomputing, Vol. 66, No. 3, 22.04.2013, p. 1462-1488.

Research output: Contribution to journalArticleResearchpeer-review

TY - JOUR

T1 - Distributed workflow mapping algorithm for maximized reliability under end-to-end delay constraint

AU - Cao, Fei

AU - Zhu, Michelle

PY - 2013/4/22

Y1 - 2013/4/22

N2 - A distributed scientific workflow mapping algorithm for maximized reliability under certain end-to-end delay (EED) bound is proposed. It is studied in a heterogeneous distributed computing environment, where computing node and communication link failures are inevitable. The mapping decision and the stored table information is distributed among various nodes in order to achieve scalability and robustness, which are especially important for large-scale distributed systems. This Distributed Reliability Maximization workflow mapping algorithm under End-to-end Delay constraint (dis-DRMED) considers both the maximum reliability and the minimum EED objectives in a two-step procedure. In the first step, a mapping algorithm combining iterative Critical Path search and Layer-based priority assigning techniques (CPL) is adopted to minimize the EED by focusing on the optimal allocation of tasks on the critical path. In the second step, tasks on noncritical paths are remapped to improve the overall execution reliability. Simulation results under various system setups demonstrated that dis-DRMED achieved considerably higher reliability values under the same EED constraint compared with some representative workflow mapping algorithms.

AB - A distributed scientific workflow mapping algorithm for maximized reliability under certain end-to-end delay (EED) bound is proposed. It is studied in a heterogeneous distributed computing environment, where computing node and communication link failures are inevitable. The mapping decision and the stored table information is distributed among various nodes in order to achieve scalability and robustness, which are especially important for large-scale distributed systems. This Distributed Reliability Maximization workflow mapping algorithm under End-to-end Delay constraint (dis-DRMED) considers both the maximum reliability and the minimum EED objectives in a two-step procedure. In the first step, a mapping algorithm combining iterative Critical Path search and Layer-based priority assigning techniques (CPL) is adopted to minimize the EED by focusing on the optimal allocation of tasks on the critical path. In the second step, tasks on noncritical paths are remapped to improve the overall execution reliability. Simulation results under various system setups demonstrated that dis-DRMED achieved considerably higher reliability values under the same EED constraint compared with some representative workflow mapping algorithms.

KW - Distributed computing

KW - Maximized reliability

KW - Minimum end-to-end delay

KW - Workflow mapping

UR - http://www.scopus.com/inward/record.url?scp=84888008807&partnerID=8YFLogxK

U2 - 10.1007/s11227-013-0938-3

DO - 10.1007/s11227-013-0938-3

M3 - Article

VL - 66

SP - 1462

EP - 1488

JO - Journal of Supercomputing

JF - Journal of Supercomputing

SN - 0920-8542

IS - 3

ER -