講演抄録/キーワード |
講演名 |
2019-12-13 09:25
反復合成を用いた1-極大独立集合問題を解く自己安定アルゴリズム ○田中秀幸・首藤裕一(阪大)・角川裕次(龍谷大)・増澤利光(阪大)・Ajoy K. Datta(UNLV) COMP2019-30 |
抄録 |
(和) |
ネットワークの1-極大独立集合を求める自己安定アルゴリズムを提案する.1-極大独立集合とは,無向グラフ(つまり,ネットワーク)$G=(V,E)$の極大独立点集合$S$であって,任意の頂点$u ¥in S, v,w ¥notin S$ ($v ¥neq w$)について$S ¥cup ¥{v,w¥} ¥setminus ¥{u¥}$が独立点集合とならないようなものである.本稿では,1-極大独立集合を求める問題に対して,グラフの各頂点が一意の識別子を持つという仮定のもと動作するサイレント(silent)な自己安定アルゴリズムを提案する.提案アルゴリズムは弱公平分散デーモンのもとで動作する.$n$をグラフの頂点数,$D$をグラフの直径とすると,収束時間は$O(nD)$であり,1頂点あたりの空間計算量は$O(¥log n)$ビットである.これらのアルゴリズムの設計にあたって,反復合成と呼ばれる手法を用いる. |
(英) |
We consider the 1-maximal independent set (1-MIS) problem: given a connected graph $G=(V,E)$, our goal is to find an 1-maximal independent set (1-MIS) of a given network $G$,
that is, a maximal independent set (MIS) $S ¥subset V$ of $G$
such that $S ¥cup ¥{v,w¥} ¥setminus ¥{u¥}$ is not an independent set for any nodes $u ¥in S$, and $v,w ¥notin S$ ($v ¥neq w$).
We give a silent, self-stabilizing, and asynchronous distributed algorithm to construct 1-MIS on a network of any topology.
We assume the processes have unique identifiers
and the scheduler is unfair and distributed.
The time complexity, i.e., the number of rounds to reach a legitimate configuration in the worst case, of the proposed algorithm is $O(nD)$, where $n$ is the number of processes in the network and $D$ is the diameter of the network.
We use a composition technique called loop composition [Datta et.al., 2017] to iterate the same procedure consistently,
which results in a small space complexity,
$O(¥log n)$ bits per process. |
キーワード |
(和) |
分散システム / 自己安定アルゴリズム / 反復合成 / 1-極大独立集合 / / / / |
(英) |
distributed system / self-stabilizing algorithm / loop composition / 1-maximal independent set / / / / |
文献情報 |
信学技報, vol. 119, no. 340, COMP2019-30, pp. 9-16, 2019年12月. |
資料番号 |
COMP2019-30 |
発行日 |
2019-12-06 (COMP) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
COMP2019-30 |
|