WEKO3
アイテム
Fast gathering despite a linear number of weakly Byzantine agents
http://hdl.handle.net/10061/0002000744
http://hdl.handle.net/10061/0002000744002fad13-3138-4dce-8978-ce702ba9f252
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
fulltext (531 KB)
|
|
| アイテムタイプ | 学術雑誌論文 / Journal Article(1) | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| 公開日 | 2025-01-21 | |||||||||
| タイトル | ||||||||||
| タイトル | Fast gathering despite a linear number of weakly Byzantine agents | |||||||||
| 言語 | ||||||||||
| 言語 | eng | |||||||||
| キーワード | ||||||||||
| 主題Scheme | Other | |||||||||
| 主題 | Byzantine environments | |||||||||
| キーワード | ||||||||||
| 主題Scheme | Other | |||||||||
| 主題 | distributed algorithms | |||||||||
| キーワード | ||||||||||
| 主題Scheme | Other | |||||||||
| 主題 | gathering | |||||||||
| キーワード | ||||||||||
| 主題Scheme | Other | |||||||||
| 主題 | mobile agents | |||||||||
| 資源タイプ | ||||||||||
| 資源タイプ | journal article | |||||||||
| アクセス権 | ||||||||||
| アクセス権 | open access | |||||||||
| 著者 |
Hirose, Jion
× Hirose, Jion
× Nakamura, Junya
× 大下, 福仁× 井上, 美智子 |
|||||||||
| 抄録 | ||||||||||
| 内容記述タイプ | Abstract | |||||||||
| 内容記述 | In this work, we study the gathering problem to make multiple agents, who are initially scattered in arbitrary networks, meet at the same node. The network has k agents with unique identifiers (IDs), and f of them are weakly Byzantine agents that behave arbitrarily, except for falsifying their identifiers. These agents behave in synchronous rounds, and they may start an algorithm at different rounds. Each agent cannot leave information at a node. We propose herein a deterministic algorithm that efficiently achieves gathering with a simultaneous termination having a small number of non-Byzantine agents. The proposed algorithm concretely works in O(f$00B7|Λall|$00B7X(N)) rounds if the agents know the upper bound N on the number of nodes, and at least 7f+7 non-Byzantine agents exist, where |Λall| is the length of the largest ID among agents, and X(n) is the number of rounds required to explore any network composed of n nodes. The literature presents two efficient gathering algorithms with a simultaneous termination. The first algorithm assumes that agents know the number n of nodes and achieves the gathering in O(n4$00B7|Λgood|$00B7X(n)) rounds in the presence of any number of Byzantine agents, where |Λgood| is the length of the largest ID among non-Byzantine agents. The second algorithm assumes both that agents know N and that at least 4f2+8f+4 non-Byzantine agents exist, and it achieves the gathering in O((f+|Λall|)$00B7X(N)) rounds. The proposed algorithm is faster than the first existing algorithm and requires fewer non-Byzantine agents than the second existing algorithm if n is given to agents. We propose herein a new technique to simulate a Byzantine consensus algorithm for synchronous message-passing systems on agent systems to reduce the number of agents. | |||||||||
| 書誌情報 |
en : Concurrency and Computation: Practice and Experience 巻 36, 号 14, 発行日 2024-06-25 |
|||||||||
| 出版者 | ||||||||||
| 出版者 | Wiley | |||||||||
| ISSN | ||||||||||
| 収録物識別子タイプ | EISSN | |||||||||
| 収録物識別子 | 1532-0634 | |||||||||
| 出版者版DOI | ||||||||||
| 関連タイプ | isVersionOf | |||||||||
| 識別子タイプ | DOI | |||||||||
| 関連識別子 | https://doi.org/10.1002/cpe.8055 | |||||||||
| 出版者版URI | ||||||||||
| 関連タイプ | isVersionOf | |||||||||
| 識別子タイプ | URI | |||||||||
| 関連識別子 | https://onlinelibrary.wiley.com/doi/full/10.1002/cpe.8055 | |||||||||
| 権利 | ||||||||||
| 権利情報 | $00A9 2024 John Wiley & Sons Ltd. This is the peer reviewed version of the following article: Hirose J., Nakamura J., Ooshita F., Inoue M., Fast gathering despite a linear number of weakly Byzantine agents. Concurrency and Computation: Practice and Experience 36, which has been published in final form at https://doi.org/10.1002/cpe.8055. This article may be used for non-commercial purposes in accordance with Wiley Terms and Conditions for Use of Self-Archived Versions. This article may not be enhanced, enriched or otherwise transformed into a derivative work, without express permission from Wiley or by statutory rights under applicable legislation. Copyright notices must not be removed, obscured or modified. The article must be linked to Wiley’s version of record on Wiley Online Library and any embedding, framing or otherwise making available the article or pages thereof by third parties from platforms, services and websites other than Wiley Online Library must be prohibited. 出版社許諾条件により、本文は2025年6月26日以降に公開 | |||||||||
| 著者版フラグ | ||||||||||
| 出版タイプ | AM | |||||||||
