Optimal task allocation and hardware redundancy policies in distributed computing systems

Research output: Contribution to journalArticle

34 Citations (Scopus)

Abstract

A distributed computing system (DCS) in general consists of processing nodes, communication channels, and tasks. Achieving a reliable DCS thus comprises three parts: the realization of reliable task processing, reliable communication among processing nodes, and a good task allocation strategy. In this study, we examine the relationship between system cost and system reliability in a cycle-free hardware-redundant DCS where multiple processors are available at each processing node and multiple communication links are available at each communication channel. Intuitively, higher hardware redundancy leads to higher system reliability which results in the reduction of communication cost. Such an endowment of hardware redundancy, however, incurs higher hardware operating cost. A unified model of system cost is therefore developed in this study that is a complex function of task allocation and hardware redundancy policies, and a hybrid genetic algorithm (HGA) based on genetic algorithms and a local search procedure is proposed to seek the optimal task allocation and hardware redundancy policies. The proposed algorithm is tested on randomly generated DCSs and compared with a simple genetic algorithm (SGA). The simulation results show that the HGA gives higher solution quality in less computational time than the SGA.

Original languageEnglish
Pages (from-to)430-447
Number of pages18
JournalEuropean Journal of Operational Research
Volume147
Issue number2
DOIs
Publication statusPublished - 2003 Jun 1

Fingerprint

Task Allocation
Distributed computer systems
Optimal Allocation
redundancy
Distributed Computing
Computer hardware
hardware
Redundancy
Computer systems
Genetic algorithms
Hardware
Processing
communication
Hybrid Genetic Algorithm
Genetic Algorithm
System Reliability
Communication Channels
Communication channels (information theory)
Costs
Vertex of a graph

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Modelling and Simulation
  • Management Science and Operations Research
  • Information Systems and Management

Cite this

@article{2dfe7ddc0fb54708a30e0c62c6593211,
title = "Optimal task allocation and hardware redundancy policies in distributed computing systems",
abstract = "A distributed computing system (DCS) in general consists of processing nodes, communication channels, and tasks. Achieving a reliable DCS thus comprises three parts: the realization of reliable task processing, reliable communication among processing nodes, and a good task allocation strategy. In this study, we examine the relationship between system cost and system reliability in a cycle-free hardware-redundant DCS where multiple processors are available at each processing node and multiple communication links are available at each communication channel. Intuitively, higher hardware redundancy leads to higher system reliability which results in the reduction of communication cost. Such an endowment of hardware redundancy, however, incurs higher hardware operating cost. A unified model of system cost is therefore developed in this study that is a complex function of task allocation and hardware redundancy policies, and a hybrid genetic algorithm (HGA) based on genetic algorithms and a local search procedure is proposed to seek the optimal task allocation and hardware redundancy policies. The proposed algorithm is tested on randomly generated DCSs and compared with a simple genetic algorithm (SGA). The simulation results show that the HGA gives higher solution quality in less computational time than the SGA.",
author = "Hsieh, {Chung Chi}",
year = "2003",
month = "6",
day = "1",
doi = "10.1016/S0377-2217(02)00456-3",
language = "English",
volume = "147",
pages = "430--447",
journal = "European Journal of Operational Research",
issn = "0377-2217",
publisher = "Elsevier",
number = "2",

}

Optimal task allocation and hardware redundancy policies in distributed computing systems. / Hsieh, Chung Chi.

In: European Journal of Operational Research, Vol. 147, No. 2, 01.06.2003, p. 430-447.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Optimal task allocation and hardware redundancy policies in distributed computing systems

AU - Hsieh, Chung Chi

PY - 2003/6/1

Y1 - 2003/6/1

N2 - A distributed computing system (DCS) in general consists of processing nodes, communication channels, and tasks. Achieving a reliable DCS thus comprises three parts: the realization of reliable task processing, reliable communication among processing nodes, and a good task allocation strategy. In this study, we examine the relationship between system cost and system reliability in a cycle-free hardware-redundant DCS where multiple processors are available at each processing node and multiple communication links are available at each communication channel. Intuitively, higher hardware redundancy leads to higher system reliability which results in the reduction of communication cost. Such an endowment of hardware redundancy, however, incurs higher hardware operating cost. A unified model of system cost is therefore developed in this study that is a complex function of task allocation and hardware redundancy policies, and a hybrid genetic algorithm (HGA) based on genetic algorithms and a local search procedure is proposed to seek the optimal task allocation and hardware redundancy policies. The proposed algorithm is tested on randomly generated DCSs and compared with a simple genetic algorithm (SGA). The simulation results show that the HGA gives higher solution quality in less computational time than the SGA.

AB - A distributed computing system (DCS) in general consists of processing nodes, communication channels, and tasks. Achieving a reliable DCS thus comprises three parts: the realization of reliable task processing, reliable communication among processing nodes, and a good task allocation strategy. In this study, we examine the relationship between system cost and system reliability in a cycle-free hardware-redundant DCS where multiple processors are available at each processing node and multiple communication links are available at each communication channel. Intuitively, higher hardware redundancy leads to higher system reliability which results in the reduction of communication cost. Such an endowment of hardware redundancy, however, incurs higher hardware operating cost. A unified model of system cost is therefore developed in this study that is a complex function of task allocation and hardware redundancy policies, and a hybrid genetic algorithm (HGA) based on genetic algorithms and a local search procedure is proposed to seek the optimal task allocation and hardware redundancy policies. The proposed algorithm is tested on randomly generated DCSs and compared with a simple genetic algorithm (SGA). The simulation results show that the HGA gives higher solution quality in less computational time than the SGA.

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

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

U2 - 10.1016/S0377-2217(02)00456-3

DO - 10.1016/S0377-2217(02)00456-3

M3 - Article

AN - SCOPUS:0037410519

VL - 147

SP - 430

EP - 447

JO - European Journal of Operational Research

JF - European Journal of Operational Research

SN - 0377-2217

IS - 2

ER -