| 講演名 | 1999/4/23 トーラス上の局所多数決と大域多数決 今林 裕, 朝廣 雄一, 山下 雅史, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 分散システムにおいて, 大域的に多数を占める意見に全てのプロセッサが合意する方法, 言い替えれば各プロセッサが多数意見を正しく知る方法を考える. ただし各プロセッサは自分の近傍のプロセッサの意見だけしか参照することができないと仮定する. 問題を以下のようにグラフ問題として定式化する. グラフG(V, E)によって分散システムをモデル化する. 頂点集合でプロセッサ集合を, 無向枝集合で双方向通信リンク集合を表す. したがって頂点vは(自分自身を含む)近傍Γ(v)={v}∪{u∈V∣{u, v} ∈ E}に属する頂点と直接情報交換が可能である. 各頂点(プロセッサ)v ∈ Vは(時刻0に)その意見を表す0か1のいずれかをその初期状態として持つ. そして各頂点vは各時刻t=1,2,...に同期的に自分の近傍において多数を占める値に自分の状態を更新する. この状態遷移を何回か繰り返した後に全ての頂点の状態が0となるとき, (初期状態において)状態1の頂点の集合は状態0の頂点の集合に支配されているという. 本稿では, トーラスを対象として被支配頂点数の最大値について検討する. |
| 抄録(英) | In distributed systems we are interested in a method for all processors to agree on the global majority opinion, despite that each processor can observe only the opinions of its neighbors. Let G(V, E) be a finite graph and consider it as a model of a distributed system. Let Γ(v)={v}∪{u∈V∣{u, v} ∈ E} denote the neighbors of v. Every vertex of synchronously updates its opinion value to the majority value of its neighbors' at time instant t=1, 2,..., when either 0 or 1 is assigned to each vertex as its initial opinion at time instant 0. The set of 0 vertices in the initial configuration is said to control the set of 1 vertices, if all vertices will have value 0 simultaneously. This paper investigates the maximum size of a controlled set of vertices on the torus. |
| キーワード(和) | 分散計算 / 局所多数決 / 大域多数決 / グラフ理論 / 合意問題 |
| キーワード(英) | distributed computing / local majority voting / global majority voting / graph theory / agreement problem |
| 資料番号 | COMP99-7 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 1999/4/23(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | トーラス上の局所多数決と大域多数決 |
| サブタイトル（和） | |
| タイトル（英） | Local and Global Majority Voting Schemes on the Torus |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 分散計算 / distributed computing |
| キーワード(2)（和/英） | 局所多数決 / local majority voting |
| キーワード(3)（和/英） | 大域多数決 / global majority voting |
| キーワード(4)（和/英） | グラフ理論 / graph theory |
| キーワード(5)（和/英） | 合意問題 / agreement problem |
| 第 1 著者 氏名（和/英） | 今林 裕 / Hiroshi IMAHAYASHI |
| 第 1 著者 所属（和/英） | 九州大学大学院システム情報科学研究科情報工学専攻 Department of Computer Science and Communication Engineering, Kyushu University |
| 第 2 著者 氏名（和/英） | 朝廣 雄一 / Yuichi ASAHIRO |
| 第 2 著者 所属（和/英） | 九州大学大学院システム情報科学研究科情報工学専攻 Department of Computer Science and Communication Engineering, Kyushu University |
| 第 3 著者 氏名（和/英） | 山下 雅史 / Masafumi YAMASHITA |
| 第 3 著者 所属（和/英） | 九州大学大学院システム情報科学研究科情報工学専攻 Department of Computer Science and Communication Engineering, Kyushu University |
| 発表年月日 | 1999/4/23 |
| 資料番号 | COMP99-7 |
| 巻番号（vol） | vol.99 |
| 号番号（no） | 30 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |