WEKO3
アイテム
Communication-efficient self-stabilizing protocols for spanning-tree construction
https://nitech.repo.nii.ac.jp/records/3592
https://nitech.repo.nii.ac.jp/records/35920f7bb209-5edc-4edd-a7e6-9fc2868b0bdf
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
本文_fulltext (185.3 kB)
|
Copyright 2009 Springer-Verlag The final publication is available at www.springerlink.com.
|
| Item type | 学術雑誌論文 / Journal Article(1) | |||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 公開日 | 2013-06-25 | |||||||||||||||||||
| タイトル | ||||||||||||||||||||
| タイトル | Communication-efficient self-stabilizing protocols for spanning-tree construction | |||||||||||||||||||
| 言語 | en | |||||||||||||||||||
| 言語 | ||||||||||||||||||||
| 言語 | eng | |||||||||||||||||||
| 資源タイプ | ||||||||||||||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||||||||||||||||
| 資源タイプ | journal article | |||||||||||||||||||
| 著者 |
泉, 泰介
× 泉, 泰介
× Masuzawa, Toshimitsu
× Katayama, Yoshiaki
× Wada, Koichi
|
|||||||||||||||||||
| 著者別名 | ||||||||||||||||||||
| 姓名 | Izumi, Taisuke | |||||||||||||||||||
| 言語 | en | |||||||||||||||||||
| 姓名 | 泉, 泰介 | |||||||||||||||||||
| 言語 | ja | |||||||||||||||||||
| 姓名 | イズミ, タイスケ | |||||||||||||||||||
| 言語 | ja-Kana | |||||||||||||||||||
| 著者別名 | ||||||||||||||||||||
| 姓名 | 片山, 善章 | |||||||||||||||||||
| 著者別名 | ||||||||||||||||||||
| 姓名 | 和田, 幸一 | |||||||||||||||||||
| bibliographic_information |
en : Proceedings of the 13th International Conference on Principles of Distributed Systems(OPODIS), Lecture Notes in Computer Science 巻 5923/2009, p. 219-224, 発行日 2009 |
|||||||||||||||||||
| 出版者 | ||||||||||||||||||||
| 出版者 | Springer Verlag | |||||||||||||||||||
| 言語 | en | |||||||||||||||||||
| ISSN | ||||||||||||||||||||
| 収録物識別子タイプ | ISSN | |||||||||||||||||||
| 収録物識別子 | 0302-9743 | |||||||||||||||||||
| ISBN | ||||||||||||||||||||
| 識別子タイプ | ISBN | |||||||||||||||||||
| 関連識別子 | 9783642108761 | |||||||||||||||||||
| item_10001_relation_32 | ||||||||||||||||||||
| 識別子タイプ | NCID | |||||||||||||||||||
| 関連識別子 | BB02048949 | |||||||||||||||||||
| 出版タイプ | ||||||||||||||||||||
| 出版タイプ | AM | |||||||||||||||||||
| 出版タイプResource | http://purl.org/coar/version/c_ab4af688f83e57aa | |||||||||||||||||||
| item_10001_relation_34 | ||||||||||||||||||||
| 関連タイプ | isVersionOf | |||||||||||||||||||
| 識別子タイプ | DOI | |||||||||||||||||||
| 関連識別子 | http://dx.doi.org/10.1007/978-3-642-10877-8_18 | |||||||||||||||||||
| 関連名称 | 10.1007/978-3-642-10877-8_18 | |||||||||||||||||||
| 内容記述 | ||||||||||||||||||||
| 内容記述タイプ | Other | |||||||||||||||||||
| 内容記述 | A self-stabilizing protocol can eventually recover its intended behavior even when startedfrom an arbitrary configuration. Most of self-stabilizing protocols require every pair of neighboringprocesses to communicate with each other repeatedly and forever even after converging tolegitimate configurations. Such permanent communication impairs efficiency, but is necessary innature of self-stabilization: if we allow a process to stop its communication with other processes,the process may initially start and remain forever at a state inconsistent with the states of otherprocesses. So it is challenging to minimize the number of process pairs communicating afterconvergence.We investigate possibility of communication-efficient self-stabilization, which allows onlyO(n) pairs of neighboring processes to communicate repeatedly after convergence. For spanningtreeconstruction, we show the following results: (a) communication-efficiency is attainablewhen a unique root is designated a priori, (b) communication-efficiency is impossible to attainwhen each process has a unique identifier but without a designated unique root, and (c)communication-efficiency becomes attainable with process identifiers if each process initiallyknows an upper bound of the network size. | |||||||||||||||||||
| 言語 | en | |||||||||||||||||||
