For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Optimal k-Bounded Placement of Resources in Distributed Computing Systems
Jong-Hoon KIM Cheol-Hoon LEE
IEICE TRANSACTIONS on Information and Systems
Publication Date: 2000/07/25
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Theory/Models of Computation
A* Algorithm, interprocessor communication, distributed computing systems, k-bounded resource placement, k-dominating sets, state-space search,
Full Text: PDF(450.7KB)>>
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 k1 of at least one resource copy, which is called the 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.