A fault-tolerant workflow mapping algorithm under end-to-end delay constraint

Fei Cao, Michelle Zhu

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearchpeer-review

4 Citations (Scopus)

Abstract

In recent years, distributed scientific workflows structured as directed acyclic graph (DAG) are widely applied to various research areas to enable science discovery. In a heterogeneous distributed computing environment, computing nodes and communication link failures are inevitable and could have an negative impact on the applications. Efficient mapping and scheduling algorithms to achieve both the low end-to-end delay and the high reliability have been attracting active research interests. However, it is not possible to optimize both objectives due to conflicting requirements. We proposed a mapping and scheduling algorithm, namely Fault-tolerant Workflow Mapping Algorithm under End-to-end Delay Constraint (FMEDC), which considers both the execution delay and reliability in a two-step procedure. In the first step, a hybrid mapping algorithm combining recursive critical path searching and layer-based priority techniques (HCPT) is developed to achieve the minimum end-to-end delay(MED) along the critical path. The computation and communication failure rates are factored into equation to compute the reliability-enhanced execution time. In the second step, the modules on the non-critical paths are rescheduled onto nodes in a way such that system reliability can be improved under the MED constraint calculated in the first step. Experimental results show that our algorithm achieves the lowest MED but highest reliability under the same time constraints compared with some representative algorithms.

Original languageEnglish
Title of host publicationProc.- 2011 IEEE International Conference on HPCC 2011 - 2011 IEEE International Workshop on FTDCS 2011 - Workshops of the 2011 Int. Conf. on UIC 2011- Workshops of the 2011 Int. Conf. ATC 2011
Pages575-580
Number of pages6
DOIs
StatePublished - 24 Nov 2011
Event13th IEEE International Workshop on FTDCS 2011, the 8th International Conference on ATC 2011, the 8th International Conference on UIC 2011 and the 13th IEEE International Conference on HPCC 2011 - Banff, AB, Canada
Duration: 2 Sep 20114 Sep 2011

Publication series

NameProc.- 2011 IEEE International Conference on HPCC 2011 - 2011 IEEE International Workshop on FTDCS 2011 -Workshops of the 2011 Int. Conf. on UIC 2011- Workshops of the 2011 Int. Conf. ATC 2011

Other

Other13th IEEE International Workshop on FTDCS 2011, the 8th International Conference on ATC 2011, the 8th International Conference on UIC 2011 and the 13th IEEE International Conference on HPCC 2011
CountryCanada
CityBanff, AB
Period2/09/114/09/11

Fingerprint

Scheduling algorithms
Distributed computer systems
Telecommunication links
Communication

Keywords

  • directed acyclic graph
  • distributed computing
  • end-to-end delay
  • mapping and scheduling
  • reliability

Cite this

Cao, F., & Zhu, M. (2011). A fault-tolerant workflow mapping algorithm under end-to-end delay constraint. In Proc.- 2011 IEEE International Conference on HPCC 2011 - 2011 IEEE International Workshop on FTDCS 2011 - Workshops of the 2011 Int. Conf. on UIC 2011- Workshops of the 2011 Int. Conf. ATC 2011 (pp. 575-580). [6063042] (Proc.- 2011 IEEE International Conference on HPCC 2011 - 2011 IEEE International Workshop on FTDCS 2011 -Workshops of the 2011 Int. Conf. on UIC 2011- Workshops of the 2011 Int. Conf. ATC 2011). https://doi.org/10.1109/HPCC.2011.81
Cao, Fei ; Zhu, Michelle. / A fault-tolerant workflow mapping algorithm under end-to-end delay constraint. Proc.- 2011 IEEE International Conference on HPCC 2011 - 2011 IEEE International Workshop on FTDCS 2011 - Workshops of the 2011 Int. Conf. on UIC 2011- Workshops of the 2011 Int. Conf. ATC 2011. 2011. pp. 575-580 (Proc.- 2011 IEEE International Conference on HPCC 2011 - 2011 IEEE International Workshop on FTDCS 2011 -Workshops of the 2011 Int. Conf. on UIC 2011- Workshops of the 2011 Int. Conf. ATC 2011).
@inproceedings{219281fc2fe84db78b1cf5202fc2bfcb,
title = "A fault-tolerant workflow mapping algorithm under end-to-end delay constraint",
abstract = "In recent years, distributed scientific workflows structured as directed acyclic graph (DAG) are widely applied to various research areas to enable science discovery. In a heterogeneous distributed computing environment, computing nodes and communication link failures are inevitable and could have an negative impact on the applications. Efficient mapping and scheduling algorithms to achieve both the low end-to-end delay and the high reliability have been attracting active research interests. However, it is not possible to optimize both objectives due to conflicting requirements. We proposed a mapping and scheduling algorithm, namely Fault-tolerant Workflow Mapping Algorithm under End-to-end Delay Constraint (FMEDC), which considers both the execution delay and reliability in a two-step procedure. In the first step, a hybrid mapping algorithm combining recursive critical path searching and layer-based priority techniques (HCPT) is developed to achieve the minimum end-to-end delay(MED) along the critical path. The computation and communication failure rates are factored into equation to compute the reliability-enhanced execution time. In the second step, the modules on the non-critical paths are rescheduled onto nodes in a way such that system reliability can be improved under the MED constraint calculated in the first step. Experimental results show that our algorithm achieves the lowest MED but highest reliability under the same time constraints compared with some representative algorithms.",
keywords = "directed acyclic graph, distributed computing, end-to-end delay, mapping and scheduling, reliability",
author = "Fei Cao and Michelle Zhu",
year = "2011",
month = "11",
day = "24",
doi = "10.1109/HPCC.2011.81",
language = "English",
isbn = "9780769545387",
series = "Proc.- 2011 IEEE International Conference on HPCC 2011 - 2011 IEEE International Workshop on FTDCS 2011 -Workshops of the 2011 Int. Conf. on UIC 2011- Workshops of the 2011 Int. Conf. ATC 2011",
pages = "575--580",
booktitle = "Proc.- 2011 IEEE International Conference on HPCC 2011 - 2011 IEEE International Workshop on FTDCS 2011 - Workshops of the 2011 Int. Conf. on UIC 2011- Workshops of the 2011 Int. Conf. ATC 2011",

}

Cao, F & Zhu, M 2011, A fault-tolerant workflow mapping algorithm under end-to-end delay constraint. in Proc.- 2011 IEEE International Conference on HPCC 2011 - 2011 IEEE International Workshop on FTDCS 2011 - Workshops of the 2011 Int. Conf. on UIC 2011- Workshops of the 2011 Int. Conf. ATC 2011., 6063042, Proc.- 2011 IEEE International Conference on HPCC 2011 - 2011 IEEE International Workshop on FTDCS 2011 -Workshops of the 2011 Int. Conf. on UIC 2011- Workshops of the 2011 Int. Conf. ATC 2011, pp. 575-580, 13th IEEE International Workshop on FTDCS 2011, the 8th International Conference on ATC 2011, the 8th International Conference on UIC 2011 and the 13th IEEE International Conference on HPCC 2011, Banff, AB, Canada, 2/09/11. https://doi.org/10.1109/HPCC.2011.81

A fault-tolerant workflow mapping algorithm under end-to-end delay constraint. / Cao, Fei; Zhu, Michelle.

Proc.- 2011 IEEE International Conference on HPCC 2011 - 2011 IEEE International Workshop on FTDCS 2011 - Workshops of the 2011 Int. Conf. on UIC 2011- Workshops of the 2011 Int. Conf. ATC 2011. 2011. p. 575-580 6063042 (Proc.- 2011 IEEE International Conference on HPCC 2011 - 2011 IEEE International Workshop on FTDCS 2011 -Workshops of the 2011 Int. Conf. on UIC 2011- Workshops of the 2011 Int. Conf. ATC 2011).

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearchpeer-review

TY - GEN

T1 - A fault-tolerant workflow mapping algorithm under end-to-end delay constraint

AU - Cao, Fei

AU - Zhu, Michelle

PY - 2011/11/24

Y1 - 2011/11/24

N2 - In recent years, distributed scientific workflows structured as directed acyclic graph (DAG) are widely applied to various research areas to enable science discovery. In a heterogeneous distributed computing environment, computing nodes and communication link failures are inevitable and could have an negative impact on the applications. Efficient mapping and scheduling algorithms to achieve both the low end-to-end delay and the high reliability have been attracting active research interests. However, it is not possible to optimize both objectives due to conflicting requirements. We proposed a mapping and scheduling algorithm, namely Fault-tolerant Workflow Mapping Algorithm under End-to-end Delay Constraint (FMEDC), which considers both the execution delay and reliability in a two-step procedure. In the first step, a hybrid mapping algorithm combining recursive critical path searching and layer-based priority techniques (HCPT) is developed to achieve the minimum end-to-end delay(MED) along the critical path. The computation and communication failure rates are factored into equation to compute the reliability-enhanced execution time. In the second step, the modules on the non-critical paths are rescheduled onto nodes in a way such that system reliability can be improved under the MED constraint calculated in the first step. Experimental results show that our algorithm achieves the lowest MED but highest reliability under the same time constraints compared with some representative algorithms.

AB - In recent years, distributed scientific workflows structured as directed acyclic graph (DAG) are widely applied to various research areas to enable science discovery. In a heterogeneous distributed computing environment, computing nodes and communication link failures are inevitable and could have an negative impact on the applications. Efficient mapping and scheduling algorithms to achieve both the low end-to-end delay and the high reliability have been attracting active research interests. However, it is not possible to optimize both objectives due to conflicting requirements. We proposed a mapping and scheduling algorithm, namely Fault-tolerant Workflow Mapping Algorithm under End-to-end Delay Constraint (FMEDC), which considers both the execution delay and reliability in a two-step procedure. In the first step, a hybrid mapping algorithm combining recursive critical path searching and layer-based priority techniques (HCPT) is developed to achieve the minimum end-to-end delay(MED) along the critical path. The computation and communication failure rates are factored into equation to compute the reliability-enhanced execution time. In the second step, the modules on the non-critical paths are rescheduled onto nodes in a way such that system reliability can be improved under the MED constraint calculated in the first step. Experimental results show that our algorithm achieves the lowest MED but highest reliability under the same time constraints compared with some representative algorithms.

KW - directed acyclic graph

KW - distributed computing

KW - end-to-end delay

KW - mapping and scheduling

KW - reliability

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

U2 - 10.1109/HPCC.2011.81

DO - 10.1109/HPCC.2011.81

M3 - Conference contribution

SN - 9780769545387

T3 - Proc.- 2011 IEEE International Conference on HPCC 2011 - 2011 IEEE International Workshop on FTDCS 2011 -Workshops of the 2011 Int. Conf. on UIC 2011- Workshops of the 2011 Int. Conf. ATC 2011

SP - 575

EP - 580

BT - Proc.- 2011 IEEE International Conference on HPCC 2011 - 2011 IEEE International Workshop on FTDCS 2011 - Workshops of the 2011 Int. Conf. on UIC 2011- Workshops of the 2011 Int. Conf. ATC 2011

ER -

Cao F, Zhu M. A fault-tolerant workflow mapping algorithm under end-to-end delay constraint. In Proc.- 2011 IEEE International Conference on HPCC 2011 - 2011 IEEE International Workshop on FTDCS 2011 - Workshops of the 2011 Int. Conf. on UIC 2011- Workshops of the 2011 Int. Conf. ATC 2011. 2011. p. 575-580. 6063042. (Proc.- 2011 IEEE International Conference on HPCC 2011 - 2011 IEEE International Workshop on FTDCS 2011 -Workshops of the 2011 Int. Conf. on UIC 2011- Workshops of the 2011 Int. Conf. ATC 2011). https://doi.org/10.1109/HPCC.2011.81