講演抄録/キーワード |
講演名 |
2016-09-06 11:00
ビザンチン環境における認証機能付き白板を用いたモバイルエージェント集合アルゴリズム ○土田将司・大下福仁・井上美智子(奈良先端大) COMP2016-15 |
抄録 |
(和) |
本稿では,ビザンチン環境において,モバイルエージェントを一つのノードに集合させるアルゴリズムを提案する.提案するアルゴリズムは,各エージェントが固有のIDを持ち,各ノードには認証機能付きの白板があり,ビザンチンエージェントが高々f個存在するネットワークで,全ての正常エージェントを$O(fm)$時間で集合させることができる($m$はネットワーク中の辺の数).従来手法は白板を用いずに$tilde O(n^9lambda)$時間($n$はノード数,$lambda$は最長IDの長さ)で集合を実現しており,提案手法は白板を用いることで大きく集合に要する時間を削減する. |
(英) |
We propose an algorithm for the gathering problem of mobile agents in Byzantine environments. The proposed algorithm can make all correct agents to meet at a single node in $O(fm)$ time ($m$ is the number of edges) under the assumption that each agent has unique ID and behaves synchronously, each node is equipped with an authenticated whiteboard, and at most $f$ Byzantine agents exist. Since the existing algorithm achieves gathering without a whiteboard in $tilde O(n^9lambda)$ time, where $n$ is the number of nodes and $lambda$ is the length of the longest ID, our algorithm shows a whiteboard can significantly reduce the time for the gathering problem in Byzantine environments. |
キーワード |
(和) |
モバイルエージェント / 集合問題 / ビザンチン故障 / / / / / |
(英) |
Mobile Agent / Gathering Problem / Byzantine Fault / / / / / |
文献情報 |
信学技報, vol. 116, no. 211, COMP2016-15, pp. 7-14, 2016年9月. |
資料番号 |
COMP2016-15 |
発行日 |
2016-08-30 (COMP) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
COMP2016-15 |