| Presentation | 2002/5/17 A method for evaluating time complexity of distributed algorithms on the asynchronous state-communication model Yoshihiro NAKAMINAMI, Toshimitsu MASUZAWA, |
|---|---|
| PDF Download Page | PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | DiDistributed systems are commonly modeled by asynchronous models where no assumption is made about process execution speed. The asynchronous model is preferable to the synchronous one because the model reflects the fact that a distributed system consists of computers with different process speed. However, the asynchrony of the system makes it difficult to evaluate time complexity of distributed algorithms. In this paper, we define linear state-transition algorithms, a class of distributed algorithms, in the state-communication model and show that (ideal) time complexity of the algorithms in the asynchronous distributed model is derived from analysis of their synchronous execution, where all processes are synchronized in the lock-step fashion. This provides an effective method for evaluating time complexity of the linear state-transition algorithms in the asynchronous distributed model. We also demonstrate the effectiveness of the method by applying it to the self-stabilizing alternator. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | distributed system / distributed algorithm / asynchronous model / time complexity / synchronous execution / linear state-transition algorithm |
| Paper # | COMP 2002-9 |
| Date of Issue |
| Conference Information | |
| Committee | COMP |
|---|---|
| Conference Date | 2002/5/17(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 | Theoretical Foundations of Computing (COMP) |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | A method for evaluating time complexity of distributed algorithms on the asynchronous state-communication model |
| Sub Title (in English) | |
| Keyword(1) | distributed system |
| Keyword(2) | distributed algorithm |
| Keyword(3) | asynchronous model |
| Keyword(4) | time complexity |
| Keyword(5) | synchronous execution |
| Keyword(6) | linear state-transition algorithm |
| 1st Author's Name | Yoshihiro NAKAMINAMI |
| 1st Author's Affiliation | Graduate School of Engineering Science, Osaka University() |
| 2nd Author's Name | Toshimitsu MASUZAWA |
| 2nd Author's Affiliation | Graduate School of Engineering Science, Osaka University |
| Date | 2002/5/17 |
| Paper # | COMP 2002-9 |
| Volume (vol) | vol.102 |
| Number (no) | 90 |
| Page | pp.pp.- |
| #Pages | 8 |
| Date of Issue | |