| Presentation | 1993/5/27 An Experimental Evaluation and Improvement of Self-Stabilizing Mutual Exclusion Algorithm Narutoshi Umemoto, Hirotsugu Kakugawa, Masafumi Yamashita, |
|---|---|
| PDF Download Page | PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | Self-stabilizing algorithms are distributed algorithms that can be staxted from any network configulation and can rearch a legitimate configulation within a finite period.Dolev et al. proposed a self-stabilizing mutual exclusion algorithm£1!which wor ks on any network topology.This algorithm consists of a spanning tree algorithm and a mutual exclusion algorithm.In this paper,we investigate the relationship between network topologies and atomic steps(period)necessary to stabilize.We show that binary trees require less atomic steps for mutual exclusion by computer simulation.Then,we propose a self-stabilizing binary spanning tree algorithm which works on complete networks and show its correctness. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | self-stabilizing / mutual exclusion / network topology / atomic step / spanning tree |
| Paper # | COMP93-16,SS93-10 |
| Date of Issue |
| Conference Information | |
| Committee | COMP |
|---|---|
| Conference Date | 1993/5/27(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) | An Experimental Evaluation and Improvement of Self-Stabilizing Mutual Exclusion Algorithm |
| Sub Title (in English) | |
| Keyword(1) | self-stabilizing |
| Keyword(2) | mutual exclusion |
| Keyword(3) | network topology |
| Keyword(4) | atomic step |
| Keyword(5) | spanning tree |
| 1st Author's Name | Narutoshi Umemoto |
| 1st Author's Affiliation | Faculty of Engineering,Hiroshima University() |
| 2nd Author's Name | Hirotsugu Kakugawa |
| 2nd Author's Affiliation | Faculty of Engineering,Hiroshima University |
| 3rd Author's Name | Masafumi Yamashita |
| 3rd Author's Affiliation | Faculty of Engineering,Hiroshima University |
| Date | 1993/5/27 |
| Paper # | COMP93-16,SS93-10 |
| Volume (vol) | vol.93 |
| Number (no) | 81 |
| Page | pp.pp.- |
| #Pages | 8 |
| Date of Issue | |