講演抄録/キーワード |
講演名 |
2007-03-05 10:00
Emulation of Ring Protocols on Trees Preserving Fault-Containment ○Yukiko Yamauchi・Toshimitsu Masuzawa(Osaka Univ.)・Doina Bein(Univ. of Texas) |
抄録 |
(和) |
自己安定プロトコルは任意の数のプロセスの一時故障からの自律的な
復帰を保証する.
実際のシステムでは少数のプロセスの一時故障からの迅速な
復帰を保証する故障封じ込めの性質がより必要とされている.
本稿では,任意の木ネットワーク上での故障封じ込めリングプロトコルの
エミュレーションを実現する手法を提案する.
提案手法は任意の木ネットワークに対して
木上の1つの実プロセスが,リング上の1つの仮想プロセスに対応するリングを
埋め込む.これにより,1つの実プロセスの一時故障がリング上の1つの
仮想プロセスの一時故障として扱える.
さらに,リング上の仮想リンクを木ネットワーク上に実現し,
リングプロトコルのエミュレーションを実現する自己安定プロトコルRETを
提案する.
本稿で定義するエミュレーションの概念はLynchが相異なる
プロトコルの対応する状況に対して定義したシミュレーションの概念よりも
一般的な概念である. |
(英) |
A desired property of a distributed, self-stabilizing protocol is
to minimize the impact of faults that can corrupt the data stored locally at some process(es), called fault-containment.
We consider emulation of fault-containing ring protocols on
tree networks.
We propose a novel ring embedding on an arbitrary tree in which
each process in the tree appears on the virtual ring as a single virtual
process.
We also propose a self-stabilizing protocol RET that emulates
ring protocols on the embedded ring with preserving the fault-containment property.
The notion of emulation is more general than the notion of simulation,
defined by Lynch over the set of configurations of two different
protocols. |
キーワード |
(和) |
分散アルゴリズム / 故障封じ込め / 故障耐性 / リング埋め込み / 自己安定 / 仮想リング / / |
(英) |
distributed algorithm / fault-containment / fault tolerance / ring embedding / self-stabilization / virtual ring / / |
文献情報 |
信学技報, vol. 106, no. 566, COMP2006-52, pp. 13-20, 2007年3月. |
資料番号 |
COMP2006-52 |
発行日 |
2007-02-26 (COMP) |
ISSN |
Print edition: ISSN 0913-5685 |
PDFダウンロード |
|