| Presentation | 2001/1/15 Constructing Optimal κ-Coteries in General Networks Eunhey Choi, Tatsuhiro Tsuchiya, Tohru Kikuno, |
|---|---|
| PDF Download Page | PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | The κ-mutual exclusion is the problem of guaranteeing that no more than κ computing nodes enter a critical section simultaneously in a distributed system. The use of a κ-coterie, which is a special set of node groups, is known as a robust approach to solve this problem. So far, several methods have been proposed for constructing κ-coteries that provide high availability. Although, among them, κ-majority coteries have been shown to be optimal in terms of availability for fully connected networks with completely reliable links, no construction of optimal κ-coteries has been suggested for general networks. In this paper, we propose a method for constructing optimal κ-coteries in general topology networks with unreliable nodes and links. In the proposed method, the problem of finding an optimal κ-coterie in a general network is formulated as a 0-1 integer nonlinear programming problem. To solve the formulated problem, we also propose a branch-and-bound method based on a linear programming relaxation. The feasibility of the proposed method is shown through an experiment conducted for several networks. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | κ-mutual exclusion / κ-coterie / availability / 0-1 integer programming / branch-and-bound |
| Paper # | SS2000-36 |
| Date of Issue |
| Conference Information | |
| Committee | SS |
|---|---|
| Conference Date | 2001/1/15(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 | ENG |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Constructing Optimal κ-Coteries in General Networks |
| Sub Title (in English) | |
| Keyword(1) | κ-mutual exclusion |
| Keyword(2) | κ-coterie |
| Keyword(3) | availability |
| Keyword(4) | 0-1 integer programming |
| Keyword(5) | branch-and-bound |
| 1st Author's Name | Eunhey Choi |
| 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 | 2001/1/15 |
| Paper # | SS2000-36 |
| Volume (vol) | vol.100 |
| Number (no) | 569 |
| Page | pp.pp.- |
| #Pages | 8 |
| Date of Issue | |