| Presentation | 2001/1/15 Design and Evaluation of a Boolean Function-Based Deadlock Detection Method for Concurrent Systems Yusuke Tokuda, Tatsuhiro Tsuchiya, Tohru Kikuno, |
|---|---|
| PDF Download Page | PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | In this paper, we propose a boolean function-based deadlock detection method for concurrent systems that are modeled as a set of communicating finite automata. The major problem with automated analysis of concurrent systems is dealing with state explosion problem. This problem occurs in systems with many processes that can interact with each other. Boolean function-based techniques and partial order reduction techniques are the two most common approaches to this problem. In a previous paper [5], these two approaches are compared with respect to performance in deadlock detection. However, the boolean function-based method used in this paper is flawed ; thus the results are not reliable. In this paper, we re-perform the comparison by developing a new boolean function-based deadlock detection method, In the method, the set of deadlock states is computed by manipulating the transition relation function, and then reachability analysis is used for deadlock detection. We implement this detection method and apply it to a variety of examples to perform comparative evaluation of these two methods. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | boolean function / concurrent system / deadlock detection / BDD / symbolic representation |
| Paper # | SS2000-34 |
| 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 | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Design and Evaluation of a Boolean Function-Based Deadlock Detection Method for Concurrent Systems |
| Sub Title (in English) | |
| Keyword(1) | boolean function |
| Keyword(2) | concurrent system |
| Keyword(3) | deadlock detection |
| Keyword(4) | BDD |
| Keyword(5) | symbolic representation |
| 1st Author's Name | Yusuke Tokuda |
| 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-34 |
| Volume (vol) | vol.100 |
| Number (no) | 569 |
| Page | pp.pp.- |
| #Pages | 8 |
| Date of Issue | |