| Presentation | 2000/1/18 Finding Optimal Resourse Allocation that Maximizes Reliability of Distributed Systems Yoshinobu Enami, Tatsuhiro Tsuchiya, Tohru Kikuno, |
|---|---|
| PDF Download Page | PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | In this paper, we present an algorithm to find an optimal solution for the k-DTA problem. The k-DTA problem is the problem of assigning k copies for each of given distributed programs and data files so as to maximize the reliability of a distributed system. This problems is known as an NP-hard problem, so the proposed algorithm employs the A^* algorithm, which has been extensively used as an effective search algorithm for such computationally intractableproblems.The A^* algorithm prunes search spaces by expanding the most promising node determined by an evaluating function. To efficiently compute the value of the evaluating function at each node, our algorithm uses boolean functions, since manipulation of boolean functions can be done very fast by means of binary decision diagrams. Through experiment using several examples, we show that the proposed algorithm expands much fewer nodes to find an optimal solution than exhaustive search. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | distributed system / k-DTA problem / A^* algorithm / evaluatin function / BDD |
| Paper # | SS99-56 |
| Date of Issue |
| Conference Information | |
| Committee | SS |
|---|---|
| Conference Date | 2000/1/18(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Software Science (SS) |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Finding Optimal Resourse Allocation that Maximizes Reliability of Distributed Systems |
| Sub Title (in English) | |
| Keyword(1) | distributed system |
| Keyword(2) | k-DTA problem |
| Keyword(3) | A^* algorithm |
| Keyword(4) | evaluatin function |
| Keyword(5) | BDD |
| 1st Author's Name | Yoshinobu Enami |
| 1st Author's Affiliation | Department of Informatics and Mathematical Science, Graduate School of Engineering Science, Osaka University() |
| 2nd Author's Name | Tatsuhiro Tsuchiya |
| 2nd Author's Affiliation | Department of Informatics and Mathematical Science, Graduate School of Engineering Science, Osaka University |
| 3rd Author's Name | Tohru Kikuno |
| 3rd Author's Affiliation | Department of Informatics and Mathematical Science, Graduate School of Engineering Science, Osaka University |
| Date | 2000/1/18 |
| Paper # | SS99-56 |
| Volume (vol) | vol.99 |
| Number (no) | 547 |
| Page | pp.pp.- |
| #Pages | 8 |
| Date of Issue | |