The search functionality is under construction.

The search functionality is under construction.

We consider the problem of placing resources in a distributed computing system so that certain performance requirements may be met while minimizing the number of resource copies needed. Resources include special I/O processors, expensive peripheral devices, or such software modules as compilers, library routines, and data files. Due to the delay in accessing each of these resources, system performance degrades as the distance between each processor and its nearest resource copy increases. Thus, every processor must be within a given distance *k**k*-bounded placement problem. The structure of a distributed computing system is represented by a graph. The *k*-bounded placement problem is first transformed into the problem of finding smallest *k*-dominating sets in a graph. Searching for smallest *k*-dominating sets is formulated as a state-space search problem. We derive heuristic information to speed up the search, which is then used to solve the problem with the well-known *A*^{*} algorithm. An illustrative example and some experimental results are presented to demonstrate the effectiveness of the heuristic search.

- Publication
- IEICE TRANSACTIONS on Information Vol.E83-D No.7 pp.1480-1487

- Publication Date
- 2000/07/25

- Publicized

- Online ISSN

- DOI

- Type of Manuscript
- PAPER

- Category
- Theory/Models of Computation

The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.

Copy

Jong-Hoon KIM, Cheol-Hoon LEE, "Optimal k-Bounded Placement of Resources in Distributed Computing Systems" in IEICE TRANSACTIONS on Information,
vol. E83-D, no. 7, pp. 1480-1487, July 2000, doi: .

Abstract: We consider the problem of placing resources in a distributed computing system so that certain performance requirements may be met while minimizing the number of resource copies needed. Resources include special I/O processors, expensive peripheral devices, or such software modules as compilers, library routines, and data files. Due to the delay in accessing each of these resources, system performance degrades as the distance between each processor and its nearest resource copy increases. Thus, every processor must be within a given distance *k**k*-bounded placement problem. The structure of a distributed computing system is represented by a graph. The *k*-bounded placement problem is first transformed into the problem of finding smallest *k*-dominating sets in a graph. Searching for smallest *k*-dominating sets is formulated as a state-space search problem. We derive heuristic information to speed up the search, which is then used to solve the problem with the well-known *A*^{*} algorithm. An illustrative example and some experimental results are presented to demonstrate the effectiveness of the heuristic search.

URL: https://global.ieice.org/en_transactions/information/10.1587/e83-d_7_1480/_p

Copy

@ARTICLE{e83-d_7_1480,

author={Jong-Hoon KIM, Cheol-Hoon LEE, },

journal={IEICE TRANSACTIONS on Information},

title={Optimal k-Bounded Placement of Resources in Distributed Computing Systems},

year={2000},

volume={E83-D},

number={7},

pages={1480-1487},

abstract={We consider the problem of placing resources in a distributed computing system so that certain performance requirements may be met while minimizing the number of resource copies needed. Resources include special I/O processors, expensive peripheral devices, or such software modules as compilers, library routines, and data files. Due to the delay in accessing each of these resources, system performance degrades as the distance between each processor and its nearest resource copy increases. Thus, every processor must be within a given distance *k**k*-bounded placement problem. The structure of a distributed computing system is represented by a graph. The *k*-bounded placement problem is first transformed into the problem of finding smallest *k*-dominating sets in a graph. Searching for smallest *k*-dominating sets is formulated as a state-space search problem. We derive heuristic information to speed up the search, which is then used to solve the problem with the well-known *A*^{*} algorithm. An illustrative example and some experimental results are presented to demonstrate the effectiveness of the heuristic search.

keywords={},

doi={},

ISSN={},

month={July},}

Copy

TY - JOUR

TI - Optimal k-Bounded Placement of Resources in Distributed Computing Systems

T2 - IEICE TRANSACTIONS on Information

SP - 1480

EP - 1487

AU - Jong-Hoon KIM

AU - Cheol-Hoon LEE

PY - 2000

DO -

JO - IEICE TRANSACTIONS on Information

SN -

VL - E83-D

IS - 7

JA - IEICE TRANSACTIONS on Information

Y1 - July 2000

AB - We consider the problem of placing resources in a distributed computing system so that certain performance requirements may be met while minimizing the number of resource copies needed. Resources include special I/O processors, expensive peripheral devices, or such software modules as compilers, library routines, and data files. Due to the delay in accessing each of these resources, system performance degrades as the distance between each processor and its nearest resource copy increases. Thus, every processor must be within a given distance *k**k*-bounded placement problem. The structure of a distributed computing system is represented by a graph. The *k*-bounded placement problem is first transformed into the problem of finding smallest *k*-dominating sets in a graph. Searching for smallest *k*-dominating sets is formulated as a state-space search problem. We derive heuristic information to speed up the search, which is then used to solve the problem with the well-known *A*^{*} algorithm. An illustrative example and some experimental results are presented to demonstrate the effectiveness of the heuristic search.

ER -