数理解析研究所講究録992 巻 1997 年 236-243236

分散相互排除システムの可用度を改善する
コーラム再割当アルゴリズム
山下雅史

原田 隆

広島大学工学部第二類

広島大学総合情報処理センター

1

はじめに

分散システムにおいて, 複数のプロセスにより共有される資源, 例えば, プロセッサ, 共有メモリ, 複製データ
ベースにおけるデータ項目など, の競合解決問題は分散相互排除問題と呼ばれる. その基本的要求は, 複数のプ
ロセスが共有資源\sim 同時にアクセスしないよう調停す.
ることである. そのような要求を満たすことを意図して作成されたアルゴリズムは, 分散相互排除アルゴリズ
ムと呼ばれる. コ一タリとは, そのアルゴリズムにおいて用いられるデータ構造であり, 互いに交わるプロセスの部分集合 (コーラムと呼ばれる) の集合である. プロ
セスが共有資源にアクセスするとき, あるコーラムに属するすべてのプロセスから許可を得なければならない
ようにすれば, 任意の 2 つのコーラムが交わることにより, 高々 1 つのプロセスしか共有資源にアクセスしないことが保証される.
コータリを用いた分散相互排除システムの特徴は耐故障性が高いことであり, これまで, 可用度に関する
コータリの特徴づけや可用度の高いコータリの構成方法などについて, 多くの研究が行なわれてきた (例えば,[1, 2, 3, 5, 6, 7] . しかしながら, それらのほとんどは分散システムのトポロジーが完全結合である場合を仮定している. トポロジーが非完全結合の場合におけるコー
タリの理論的な特性は, リングや木などの単純な場合しか明らかでなく, また, コータリ構成手法も経験主義的なものしか提案されていない.
我々はこれまで, 茨木ら [5] の提案した $G$ -支配 (Gdomination) という概念に基づき, 非完全結合ネット
ワークにおける可用度の高いコ一タリの特徴づけを行ってきた [4]. 本稿では, その特徴づけに基づいたコータリ
構成アルゴリズムを提案する. それは, 与えられたネッ
トワーク上に定義されたコータリを, そのコーラムの接続性に応じて再割り当てし, より可用度の高いコータリを得るものである. 本稿は, 以下の節から構成される.
第 2 節に必要な定義を示す. 第 3 節では, アルゴリズムの基礎となる定理について述べる. 第 4 節で 2 つのコー
ラム再割当アルゴリズムを提案し, 第 5 節でそれらの評価を行なう.
$)$

2

定義

無向グラフ $G=(V, E)$ を分散システムのトポロジーとする. ここで, 各頂点物 $\in V$ はプロセス (またはノード), 各辺 $e_{k}=(v_{i}, v_{j})\in E$ はプロセス賜と吻間の通信

リンクを表す.

を頂点の全体集合とする. 以下の式を満
定義 1[3]
たす $V$ の非空な集合 $C$ を $V$ 上のコータリという.
$V$(i) (Intersection property)(ii) (Minimality)$\forall p,$$\forall p,$$q\in C[p\cap q\neq\emptyset]$$q\in C\lceil p\not\subset q|$,.

コータリ $C$ の要素はコーラムと呼ばれる.

口

定義 2[3] $C$ と $D$ を $V$ 上のコータリとする. $C\neq D$ ,であるような $q\in C$
かつ, 任意の $p\in D$ に対して
$C$
$D$
は
を支配する
(dominate) といが存在するとき,う。 また, 他のいかなるコータリに支配されないコ一タ
コータリ (nondominated coterie) と呼ばれる.
リは,$q\subseteq p$$\mathrm{N}\mathrm{D}$口

ここで, コータリを用いた相互排除アルゴリズムの概略を述べる. 臨界領域に入ろうとするプロセス (頂点)は, いずれかのコーラムに属するすべてのプロセスから許可を得なければならない. 許可を与えたプロセスは,その許可が戻るまで別のプロセスに許可を与えないよ
うにすれば, コータリの intersection property により,同時に臨界領域に入るプロセスの数が高々 1 であることが保証される.
定義 2 はコータリの可用度と密接な関係がある. グラ
フ $G$ 上のコータリ $C$ の可用度とは, $G$ の各頂点あるいは各辺に稼働確率 (operating probability) が与えられたとき, $C$ を用いる相互排除アルゴリズムで, 少なくとも 1 っのプロセスが相互排除を実行できる確率である(故障形態は停止故障 (fail-stop) を仮定する). コータリ
$C$ がコータリ $D$ を支配するならば, 可用度の点で $C$ は$D$ よりも優れているといえる.
なぜならば, $D$ を用いる
アルゴリズムにおいて, あるプロセスが $D$ のコーラムに属するすべてのプロセスから許可を得ることに成功したとすると, $C$ を用いるアルゴリズムでも $C$ のコー
ラムに属するすべてのプロセスから必ず許可をコータリ得ることができるからである. それゆえ,のみが (可用度に関する) 最適コータリの候補となる.
$q$$q’(\subseteq q)$$\mathrm{N}\mathrm{D}$定義 2 は分散システムのトポロジーが完全結合である
場合, 可用度の高い相互排除システムを設計するための良い指標となるが、 トポロジーが非完全結合の場合には, その影響を反映することはできない. このため, 茨
木らは $G$ -支配という概念を提案し, 木およびリング型
ネットワークでの最適コータリの解析を行なった [5].

237
定義 3[5]$G=$ ( $V,$ E-) をグラフ, $C$ を $V$ 上のコータ
リとする. ある $q\in C$ に対して qVh であるような $G$のすべての連結極小部分グラフ $h=(V_{h}, E_{h})$ の集合をで示す. ここで, が極小とは, いかなるの$h$$\mathcal{H}c(C)$定理 2[5] $G=(V, E)$ をグラフ, $C$ と $D$ を $V$ 上の 2
つのコータリとする. $D$ が $C$ を $G$-支配するならば, 以
下の式が成り立つ.

$h$

真部分グラフも上の条件を満たさないことを意味する.
それゆえ,は木の集合である.
に属する木のうち, その真部分木もまた$A_{G}(C)\leq A_{G}(D)$.

$\mathcal{H}c(C)$口$\mathcal{H}c(C)$に属しているような木をから取り除いた結果得られる集合 (の部分集合) をで示す. ならば,に属する任意の相異なる 2 つの木 , んに対し, が の部分グラフである, という関係の minimality とは成り立たない. この性質を$\mathcal{H}c(C)$$\mathcal{H}_{G}(C)$$\mathcal{H}_{G}(c)$$\mathcal{H}_{G}^{*}(C)$$\mathcal{H}_{G(C)}^{*}$

$g$

$h$

$g$

$\mathcal{H}_{G}^{*}(C)$呼ぶ口

定義 4[5] $G=(V, E)$ をグラフ, $C$ と $D$ を $V$ 上の一タリとする.
, かつ, 任2 つの$\text{コ}$$?t_{G}^{*}(C)\neq \mathcal{H}_{G}^{*}(D)$

意の
が
に対して
の部分木であるようなが存在するとき, $C$ は $D$ を G-支配する (G-dominate) という。 また, 他のいかなるコータ$h$$g\in \mathcal{H}_{G}^{*}(D)$$g$$h\in \mathcal{H}_{G}^{*}(C)$

リに $G$-支配されないコータリは, G-ND コータリ

nondominated coterie) と呼ばれる.

以下の定理 3 および 4 は, それぞれ, グラフ 上のコー
タリが他のコータリから G-支配されるための必要十分
条件と十分条件を与える. 定理 4 は必要条件ではないが,定理 3 に比べてより少ない計算量で -支配性のチエ ‘ノ ‘
クができる. 今回提案するアルゴリズムのひとつは定理
4 に基づいている. なお, 証明は [4] を参照のこと.
$G$

$G$

定理 3[4] $G=(V, E)$ をグラフ, $C$ を 上のコータリとする. 以下の式を満たす $f=(V_{f}, E_{f})\in \mathcal{T}(G)$ が存在するとき, およびそのときに限り, $C$ は他のコータリから G-支配される.
$V$(G任意の $h=(V_{h}, E_{h})\in \mathcal{H}_{G}^{*}(C)$ に対し,口

コータリ $C$ がコータリ $D$ を $G$-支配するならば, グラ$h\not\subset f$

かつ$V_{h}\cap V_{f}\neq\emptyset$.

(1)

フ $G$ において, $C$ を用いるアルゴリズムは $D$ を用いる

ものよりも高い可用度を持つことが保証される. また,
コータリと同様に, G-ND コータリのみが $G$ 上の最
適コータリの候補となる.

口$\mathrm{N}\mathrm{D}$を $V$ の非空な部分集合の集合とする. $Q$ に
定義 5
属する要素のうち, その真部分集合もまた $Q$ に属しているような要素を $Q$ から取り除いた結果得られる集合を$MinSet(Q)$ で示す. ある $q\in Q$ に対し,である
$Q$

$q\subseteq r$

ような $V$ のすべての部分集合
で示す

定義 6
る.

$C$

を $V$ 上のコータリ,$r$の集合を $Maxs_{e}t(Q)$とする. 頂点集合が であるようは自己連結であるという, さもなければ, は自己非連結であるという.
$V$の部分集合を$s$$s$

な $G$ の連結成分が存在するならば,

$s$

$s$

定理 4[4] $G=(V, E)$ をグラフ, $C$ を $V$ 上のコータリとする. 以下の式を満たすコーラム $q\in C$ が存在する
とき, $C$ は他のコータリから G-支配される.

口
$s$

$q$

を $V$ の喰頃集合とす

は自己非連結かつ,$\overline{q}$は自己連結.

という式
口
で示す.

$MinSet(\{q|q\in Maxs_{e}ts(c)\wedge q\not\subset s\})$で表される $V$ の部分集合の集合を$C\backslash \{s\}$(2)口

以下の補題 1 と 2 は, 定理 5 の証明に用いられる.

3

基本的定理

補題 1[4] $G=(V, E)$ をグラフ, $C$ を

本節では, グラフ上のコータリに関する特徴づけの結果を示す. これらは, 今回提案するアルゴリズムの基礎となるものである. なお, 以降より, グラフ $f$ が の部
分グラフ (真部分グラフ) であることを $f\subseteq g(f\subset g)$という式で表すことにする. また,という記号により, グラフ $G$ のすべての非サイクル的な連結部分グ
ラフ (すなわち, 木) の集合を示す.
$g$$\mathcal{T}(G)$定理 1 [5] $G=(V, E)$ をグラフ, $C$ と $D$ を $V$ 上の 2
つのコータリとする. $D$ が $C$ を支配するならば, 以下の式が成り立つ.

$\dot{i}$.

上のコータリに属する任意の木とする. このとき,
であるような $q\in C$ が存在するなであるような $h\in H_{G}^{*}(C)$ が存在する. 口
らば,
とする.

$f=(V_{f}, E_{f})$を$V$$\mathcal{T}(G)$$q\subseteq V_{f}$$h\subseteq f$

補題 2[3] $C$ を $V$ 上のコータリとする. 以下の式を満たすの部分集合 が存在するとき, およびそのときに限り $C$ は他のコ一タリから支配される.
$V$

$s$

任意の $q\in C$ に対し,

$q\not\subset s$

かつ $q\cap s\neq\emptyset$ .

.

(3)
口

$A_{G}(C)\leq A_{G}(D)$,

ここで, $A_{G}(C)$ はグラフ $G$ 上のコータリ $C$ の可用度を口示す.
.
$\cdot$$\cdot$定理 5 は, グラフ $G$ 上の ND コータリが他のコータ
リから $G$ -支配されるための必要十分条件であり, 今回
提案するもうひとつのアルゴリズムの基礎となる.

238
定理 5 $G=(V, E)$ をグラフ, $C$ を $V$ 上の ND コ $-$タリとする. 以下の式を満たすコーラム $q\in C$ および$G-q$ の連結成分 $W=(Vw, Ew)$ が存在するとき, お
よびそのときに限り, $C$ は他のコータリから G-支配さの生成部分木が存在し, それを $f=(V_{f}, E_{f})$ とする(すなわち, $V_{f}=V_{W}$ ).
に対してん
まず, 任意のんという関係が成り立つことを背理法により示す. んが存在すると仮定する (すなわであるようなの定義によって,
ならば
,
).
ち,
であるようなコーラム q’ が存在する. ならば,
および $V_{h}\subseteq V_{f}=Vw$ という関係より, $q\cap q’=\emptyset$ という関係が導かれ, コータリ $C$ の intersection propertyに対してんに矛盾する. ゆえに, 任意のんという関係が成り立つ.
といに対して
次に, 任意のんの任意の要素んう関係が成り立つことを示す.
の定義によりVh であるようを固定する.
なコーラム q’ が存在する. ならば, 仮定より G–Vw の$W$$=(V_{h}, E_{h})\in \mathcal{H}_{G}^{*}(C)$$\not\subset f$$\subseteq f$

れる.

$h\in \mathcal{H}_{c(C)}^{*}$

G–Vw の任意の連結成分 $W’=$ $(V_{W’} , E_{W’})$ および,任意のコーラム $p\in C$ に対して,$p\not\subset V_{W’}$(4),$q’\subseteq V_{h}$$\mathcal{H}_{G}^{*}(C)$$V_{h}\subseteq V_{f}$$q\cap V_{W}=\emptyset$$\not\subset f$$\in \mathcal{H}_{G(C)}^{*}$の部分集合) は, $V-s$ から誘導
ここで, $G-s$ ( はされる $G$ の部分グラフである.
$s$

$V$

$V_{h}\cap V_{f}\neq\emptyset$$\in \mathcal{H}_{G}^{*}(C)$$\mathcal{H}_{G(C)}^{*}$

を $G$ 上の ND コ一タリとする. ならば, 式(4) を満たす $q\in C$ と $G-q$ の連結成分 $W$ が存在する

Proof.

$C$

ことが, 定理 3 の式 (1) を満たす $G$ の部分木が存在する
ことと同値であることを示す.
は他のコータリから G-五配されると仮定
If part:に対しする. ならば, 定理 3 により任意のん$C$$\in \mathcal{H}_{G}^{*}(C)$てん$\not\subset f$

かつ $V_{h}\cap V_{f}\neq\emptyset$ であるような $G$ の部分木が存在する.
または $q\cap V_{f}=$なので補題 2 によって,
であであるようなコーラム $q\in C$ が存在する.
補題
1
によっ
$q\in
C$
が存在すると仮定すると,るようなが存在することにであるようなて,であなり, 最初の仮定に矛盾する. ゆえに,るようなコーラム $q\in C$ が存在すると仮定してよい.
まず, $G-q$ 内の連結成分について考える.
という事実より, $G-q$ 内に木 $f$ を部分グラフとして含むような連結成分が存在すると推論してよい. このような $G-q$ の連結成分を $W=(V_{W}, Ew)$ とする (すなわち, $f\subseteq W$ ). 次に, G–Vw 内の任意の連結成分を固定し, $W’=(V_{W’,w}E’)$ とする. ならば, $V_{W}\cap V_{W}’=\emptyset$が成り立つことは明らかである.
という
以下, 任意のコーラム $p\in C$ に対して関係が成り立つことを背理法により証明する.
であるような $P\in C$ が存在すると仮定する. 連結成分とす
W’ の生成部分木が存在し, それを $f’=(V_{f’},$る (すなわち, $V_{f’}=V_{W’}$ ). ならば,
, 補題
$f=(V_{f}, E_{f})$$C$は$q\subseteq V_{f}$$\mathrm{N}\mathrm{D}$$q\subseteq V_{f}$$\emptyset$$h\subseteq f$$h\in \mathcal{H}_{G}^{*}(C)$$q\cap V_{f}=\emptyset$$q’\subseteq$$\mathcal{H}_{G}^{*}(C)$と任意の連結成分 $W’=$ $(V_{W’} , V_{F’})$ に対してという関係が導かいう関係が成り立つので,は G–Vw 内のれる. このことは, 任意のん単–の連結成分内に含まれないことを意味している. しは必ず Vw $(=V_{f})$ 内のあたがって, 任意のんる頂点を含んでいなければならない. すなわち, 任意のという関係が成りん
に対して$C$のコーラムおよび立つ. 以上から, 式 (4) を満たす
$G-q$ の連結成分が存在するならば, この連結成分に対応する生成部分木に対して式 (1) が保持される, すな
わち $C$ が他のコータリから G-支配されることが示され$q’\not\subset V_{W’}$$V_{h}\not\subset V_{W’}$$\in \mathcal{H}_{G(C)}^{*}$$\in \mathcal{H}_{G}^{*}(C)$$V_{h}\cap V_{f}\neq\emptyset$$\in \mathcal{H}_{G}^{*}(C)$た口$q\cap V_{f}=\emptyset$$P\not\subset V_{W’}\vee$4

コーラム再割当アルゴリズム

まず, 与えられた頂点集合から別のコータリを構成する関数 Replace の定義を示す. これは, Pascal 風に記述したものである.

Quorum Replace Rnction$p\subseteq V_{W’}$$Ef^{\prime)}$$P\subseteq V_{f’}\text{であ}V$

1 より ん f’ であるような$\mathcal{H}_{G(C)}^{*}$の要素ん $=(V_{h}, E_{h})$$V_{f}\subseteq V_{W}(f\subseteq W$が存在する. ならば,
$V_{f’}=V_{W’}$ より) とい(んより) およびという式が導かれ, 仮定に矛う関係から,という盾する. ゆえに, 任意の $P\in C$ に対して関係が成り立つ. 以上から, $C$ が他のコータリから G支配されるならば, 式 (4) を満たす $q\in C$ および $G-q$の連結成分 $W$ が存在することが示された.
$V_{W^{\cap}}V_{W}’=\emptyset,$$V_{h}\subseteq V_{W’}$$\subseteq f’,$$V_{h}\cap V_{f}=\emptyset$: universal set of vertices;
1 function Replace ($C$ : coterie;: subset of ): coterie;
2 var$C’$ : set of subsets of;
3
4 begin;5
Replace: $=Mins_{e}\iota(C’\cup\{\overline{s}\})$
6
7 end.
$\mathrm{v}\mathrm{a}\mathrm{r}V$

$V$

$s$

$V$

$C’:=C\backslash \{_{S}\}$$P\not\subset V_{W’}$

Only if part:

式 (4) を満たす $C$ のコーラム$q$に対応する生成部分木に対して定理 3 の式 (1) が成り立つことを示す. いま, 式 (4) を満たすコーラム および$G-q$ の連結成分 $W=(Vw, Ew)$ が存在すると仮定す
$q$

る.

$s$

およ

び $G-q$ の連結成分が存在するならば, この連結成分$q\cap Vw=\emptyset$

補題 3 $V$ を頂点の全体集合, $C$ を $V$ 上のコータリとする. そして を $V$ の任意の真部分集合とする. ならば, Replace $(V, c, S)$ は $V$ 上のコータリである.

が成り立つことは明らかである. また,

Proof.

Replace $(V, c, s)$ が minimarity を満たすことは明らかである. Intersection property に関しては,$MaxSet(c’)$ は $MaxSet(c)$ の部分集合であり,なので, C’ 内の任意の 2 つの要素は互いに交わる. をなので, 寡C’ に属する任意の要素とする.

$C’\neq\emptyset$$q$$q\not\subset s$$q$$- s\neq\emptyset$

239という式が成り立つ. ゆえに,, すな

わち Replace $(V, c, S).$’ は intersection property を満たすことを示すことができる. いま,とする. C’ がコータリであることは明らかである. さらに,す

Replace 関数の定義より,$Mins_{e}\iota(C’\cup\{\overline{s}\})$

口

定理 4 をベースにしたコーラム再割当アルゴリズムを以下に示す.

Reassignment Algorithm I$c_{+1},\text{が}$$\neq\emptyset$$V_{h}\subseteq\overline{V_{f}}$$V$$\mathcal{H}_{G}^{*}(Ci)$$\mathcal{H}_{G}^{*}(c’)=\mathcal{H}_{c}*$$V$$H_{G}^{*}(c’)=\mathcal{H}_{G}^{*}(Ci)$$h\in \mathcal{H}_{G}^{*}(C’)$$\not\subset f$$C_{i+1}$

$V$

$V$

$\mathcal{H}_{G}^{*}(Ci+1)$$\mathcal{H}_{G}^{*}(C’)$$\mathcal{H}_{G}^{*}(c’)$$=\emptyset$$\mathrm{c}_{41}\text{が}$$Q\neq\emptyset$$c_{+1},\text{が}$

$Q$

$q$

$C_{i+},\text{が}$$\mathcal{H}_{G}^{*}(cr)=\mathcal{H}_{G}^{*}$$h\in \mathcal{H}_{G}^{*}$

$x$

$q$

は $MinSet(c’\cup\{V_{f}\})$ という式で表されるコ一タリである.
以下,
G を G-支配することを示すために,
C’ を G-支配する(Ci), およびことを示す.
$f$ は (1) 式を満たすので, 任意の(C のに対し$V_{h}\cap V_{f}$$(\mathrm{v}\mathrm{a}\mathrm{r}G(V, E)$$Q$$C_{i+1}$という関係が成り立つ. したがって,であるようなの要素んは存在しない.
ならば, C, から C’ の構成より,(C のという式が成り立つことは明らかである. さらに, $f$ が (1)式を満たすこと, およびより, 任意のに対しんという関係が成り立つ.
ならば, C’ からの構成より,
は,に $f$ を加え, $f$ の超グラフであるような要素をから取り除いた結果得られる集合であることは明らか
C’ を G-支配するという関であり, 定義 4 より,係が成り立つ.
したがって,Ci を G-支配することが成り立
ち, 定理 2 より $A_{G}(Ci)\leq A_{G}(c_{i+1})$ という式が成り立つ. 仮定より, $A_{G}(C)\leq A_{G}$ (Ci) なので, $A_{G}(C)\leq$$Ac(C_{i+1})$ が示された. ゆえに, 任意の $i(1\leq i\leq k)$ に口
ついて $A_{G}(C)\leq A_{G}(C_{i})$ という関係が成り立つ.

1 program Reassignmentl (INPUT, OUTPUT);
2 var$G(V, E)$ : graph; $C$ : coterie; : subset of3;
4 function $Detec\iota$: graph; $C$ : coterie):
subset of ;5 var
6check: Boolean;: set of subsets of ; {set of quorums}
7: subset of ;8{quorum}
9 begin.
$Q:=C$ , check $:=fal_{Se}$ ; Detect:
;
10
11
while
and check $=fa\iota_{S}e$ do
12
begin
13
Let be any element in , and $Q:=Q-\{q\}$ ;14
if は自己非連結 and は自己連結 then
15
begin
16
Detect: $=q$ ; check: $=true$
17
end
end
18
19 end;20 begin
21
READ $(G, C)$ ;$x:=Detec\iota(c, C)$ ;
22
while
do
23
24
begin
$C:=Rep\iota_{aC}e(V, C_{X},);x:=Deteci(G, C)$
25
$26$
end
$write\iota n(C)$27
28 end.
$q$$C’=C_{i}\backslash \{\overline{Vf}\}$$\overline{q}$以下は, 定理 5 に基づくコーラム再割当アルゴリズ
ムである.

Reassignment Algorithm II$x\neq\emptyset$

1 program Reassignment2 (INPUT, OUTPUT);
2 var$G(V, E)$ : graph; $C$ : coterie; : subset of;3
4 function: graph; $C$ : coterie):
subset of ;5 var
result, check Boolean;
6
set of subsets of ; {set of quorums}
7
set of subsets of ;8{set of vertex sets of connected components}: subset of ; {quorum}$p,$
9
10 begin$Q_{1}:=C$ ; result: $=fal_{S}e$ ;1112 . while
and result $=fa\iota_{S}e$ do
13
begin, and $Q_{1}:=Q_{1}-\{q\}$ ;14
Let be any element in
Determine the vertex setsof the components
15
of $G-q$ ;
while
16
and
.
begin
17
Let
be an arbitrary element in ,18.
and $T_{1}:=T_{1}-\{V_{W}\}$ ;Determine the vertex setsof19
the components of G–Vw;
check: $=true;$ .
20
and check $=true$ do
21
while
22
begin
be an arbitrary element in ,Let
23
and $T_{2:=}T_{2}-\{V_{W’}\}$ ;
$V$

$x$

$De\iota_{e}Ct$ $(\mathrm{v}\mathrm{a}\mathrm{r}c(V, E)$$V$

定理 6 $G=(V, E)$ をグラフ, $C$ を $V$ 上のコータリとする. $D$ を Algorithm I により $C$ から構成したコータリとする. ならば, 以下の式が成り立つ.
$A_{G}(C)\leq A_{G}(D)$

.

$j$

$V$

$Q_{1},$ $Q_{2:}$$V$$T_{1},$ $T_{2:}$

$V$

$q$

$Q_{1}\neq\emptyset$

Proof

Algorithm I の 23 行から 26 行までの while

文の実行により置き換えられ変化するコータリの列を$(C=)c_{1},$$c_{k(}=D)\dot{\text{と}する}$$c_{2},$$\ldots,$, ここで$k\geq 1$である.

ならば, 任意の $i(1\leq i\leq k)$ について $A_{G}(C)\leq A_{G}$ (Ci)という式が成り立つことを示せば十分である. 以下,に関する帰納法により証明を行なう.
$i=1$ のとき, $C=C_{1}$ より $A_{G}(C)\leq Ac(C_{1})$ が成り立つことは明らかである. 次に, $A_{G}(C)\leq A_{G}(C_{i})$ , こ
こで $1\leq i<k$ , が成り立つと仮定する. $i<^{-}k$ なので,が自己非連結かっ-q が自己連結であるようなコーラム$q\in$ ci が存在する.
ならば定理 4 の証明部分より, 頂点集合が-q であるような $G$ の部分木 $f=(V_{f}(=\overline{q}), E_{f})$に関して定理 3 の (1) 式を満たが存在し, $f$ が
$i$

$q$

$H_{G}^{*}(Ci)$$Q_{1}$$q$$T_{1}$$T_{1}\neq$$\emptyset$

r.esult$=false\dot{\mathrm{d}}\mathrm{O}$$V_{W}$$T_{1}$$T_{2}$$T_{2}\neq\emptyset$$V_{W’}$$T_{2}$

240

24
25
26.
27

$Q_{2}:=C$ ;and check $=true$ do
while
begin
.
,
Let be an arbitrary element$Q_{2}:=Q_{2}-\{p\}$ ;
and
.
if
then
. false.
end
end;
if check $=true$ then
begin
etect: $=\overline{V_{W}}\cdot,resu\iota t:=true$
end
end
end
end;
begin
$Q_{2}\neq\emptyset$

または p-x である
いずれの場合においても,ようなコーラム $p\in Rep\iota aCe(V, c, S)$ が存在することがである.
示された. したがって, Replace $(V, C, s)$ は$p\subseteq x$$\mathrm{N}\mathrm{D}$$\mathrm{i}\mathrm{n}\cdot Q_{2}$

$p$

28
29
30
31
32
33
34
35
36
37
38
) $(G, c)$ ;39$x:=Deiect(c, C)$ ;
40
do
41
while
42
begin
$C:=ReplaCe(V, c, x);x:=Detect(c, c)$
43
44
end
$write\iota n(c)$4546 end.
$p.\subseteq V_{W’}$$\mathrm{c}..he.ck:=$口

以下の定理は, Algorithm II において, 入力されるコータリがならば, 出力されるコ一タリの G-ND 性が保証されることを述べている.
$\mathrm{N}\mathrm{D}$$\grave{D}$$\dot{R}’\dot{E}Al$$x\neq\emptyset$$A_{G}(c)\leq AG(D)$ .

Proof.

定理 6 の証明における $f$ を頂点集合 rw がであるような $G$ の部分木に置き換えることにより
, 同じ論
.
口
証を用いて証明することができるので省略する.

ならば, Re以下の補題は, 入力されたコータリが性を保存することを示す.
place 関数は$\mathrm{N}\mathrm{D}$$\mathrm{N}\mathrm{D}$

補題 4 $C$ を $V$ 上のコータリ, を $V$ の任意の真部分集合とする. $C$ がならば, Reptace $(V, c, S)$ もまた
である.
$s$

$\mathrm{N}\mathrm{D}$$\mathrm{N}\mathrm{D}$$C$

が ND コータリであると仮定する.

$V$

の任意

ま
を固定する. ならば, 補題 2 より,たは(すなわち,) であるようなコーラ
ム $q\in C$ が存在する.
..
.
.
を仮定する
.
最初に,
ならば, -x である. $\overline{s}\in ReplaCe(V, c_{s},)$ なので,-x であるようなコーラム $p\in ReplaCe(V,\dot{c}_{s},)$ が存在する.
ならば, $x\in MaxSet(Rep\iota aCe(V, C_{S},).)$ となるので, ある$p\in ReplaCe(V, C, s)$ に対しという関係が成りの部分集合

Proof.

補題 4 より, コ一タリ $D$ は ND であることが保証される. ならば Algotithm II より, コータリ $D$
は定理 5 の (4) 式を満たすようなコーラム $q\in D$ およ
び $G-q$ 内の連結成分 $W$ を持たないことが明らかであ口る. ゆえに, $D$ は G-ND である.

5

定理 7 $G=(V, E)$ をグラフ, $C$ を $V$ 上の ND コータ
リとする. $D$ を Algorithm II により $C$ から構成した
コータリとする. ならば, 以下の式が成り立つ.

Proof.

定理 8 $G=(V, E)$ をグラフ, $C$ を $V$ 上の ND コータ
リとする. $D$ を Algorithm II により $C$ から構成した
コータリとする. ならば, $D$ は G-ND コータリである.

評価

本節では, コーラム再割当アルゴリズムを評価するため, ネットワークのトポロジーや入力コータリを変化させたいくつかのケースにおける計算結果を示す. 計算に用いたトポロジーを心-1 に示す. 頂点数が 7 で, 辺の数が異なる 5 種類のネットワークである. 入力コータリは,
表-1 に示される 4 つのタイプのものを用いた. ひとつのタイプのコータリには, コーラムに割り当てる頂点の組合せにより, 複数のコータリが存在する. 例えば, 頂
点数が 7 のネットワークにおける 3-Majority コ一タリ
は 7C3 個存在する. 計算では, それぞれのタイプにおけるすべてのコータリの可用度を求めたが, 以降に示す結果では, その平均値のみを掲載している. また, 各頂点の稼働確率は表-2 に示すように 2 つのケースに分かれる. いずれもすべての頂点について–様である. 非一様なケースでも計算可能であるが, トポロジ一や入力コー
タリの違いによる比較を容易にするため, 一様としている. また, 辺は故障しないものと仮定している.

$q\subseteq x$$x$$q\cap x=\emptyset$. 表 2: 稼働確率

$q\subseteq\overline{x}$$x\subseteq s$$q\subseteq x$.

ケース

各頂点\emptyset 稼働確率–..

$\overline{s}$$\sim$.

$P\subseteq$A$\mathrm{B}$$x\not\subset s$

すべて 0.8$-$

すべて 0.6$p\subseteq x$

..

立つ.

$\text{コ}$-x を仮定する.
ならば,
次に,$p\subseteqx$であるようなコーラム $p\in$であり, ゆえに$Replace(V, c_{s},)$ が存在する.
ならば, ある$P\in ReplaCe(V, c, s)_{-}$ に対しという関係が成り$q\subseteq$$\overline{x}\subseteq s$$\overline{x}\not\subset s$$P\subseteq\overline{x}$立つ.

.

$\cdot$オリジナルのコータリと再割当後の 一タリの可用度の比較を表-3 と 4 に示す. 表-3 がケース , 表-4 がケースでの計算結果である. 可用度の行には, 該当するタイプのすべてのコータリの可用度の平均値が示さ$\overline{s}\subseteq x$$\mathrm{A}$$\mathrm{B}$

れている.

計算結果から得られた考察を以下に示す.

241

図 1: トポロジー

表 1: コータリ
コータリのタイプ

例

3-Majority’35
6-Array7
5-Majority21$\{\{1,2\},\{1,3\},\{2,3\}\}$$\{\{1,2\},\{1,3\},\{1,4\},\{1,5\},\{1,6\},\{1,7\},\{2,3,4,5,6,7\}\}$,$\{\{1,2,3\},\{1,2,4\},\{1,3,4\}_{:}\{.2-,3,4\},\{1,2,5\},\{1,3,5\},\{2,3,5\}$$\{1,4,5\},\{2,4,5\},\{3,4,5\}\}$

7-Majority1$\{\{1,2,3,4\},\{1,2,3,5\},\{1,2,3,6\},\{1,2,3,7\},\{1,2,4,5\},\{1,2,4,6\}$,$\{1,2,4,7\},.\{1,2,5,6\},\{1,2,5,7\},\{1,2,6,7\},\ldots\}$$\bullet$

グラフの辺の数により改善率が異なる. 辺の最も少と最も多いで改善率が低く, 中間のない$G_{1}$

ないことによるものと思われる.

$G_{3}$$G_{\mathit{5}}$で改善率が最も高くなる傾向がある. 提案したアルゴリズムは, それ自身では非連結であるようなコー

ラムあるいはコーラムを含む頂点集合に対し, その補集合が連結ならば, コーラムをその補集合で置き換えるということを基本にしているが, 辺の数が極端に少ない場合や多い場合では, そのような状況が生じにくいためであろう.
$\bullet$

頂点の稼働確率が低いほど改善率が高い. 全体の稼働確率が高い場合, 多くの頂点が稼働している状況
ほど確率が高く, 停止している頂点が多くなるほどその確率が低くなる. -方, 全体の稼働確率が 0.5に近くなるにつれ, それらの差は小さくなる. このため, 全体の稼働確率が低くなるほど, 置き換えにより改善される可用度は多くなる.
’$\bullet$

Algorithm I と II による差は, 今回計算した中での場合でしか現れなかった. これは, 定理 4
定理 5 の (4) 式を満たすという状況は, グラフの辺が少ない場合でしか生じは,$G_{1}$の (2) 式を満たさないが,$\bullet$.

6:3-Majority や 6-Array コータリのほうが, 5Majority や 7-Majority コータリに比べて改善率が高い傾向があるが, これは, 小さなサイズのコー
ラムを多く持つコータリの方が置き換えが起こりやすいことに起因すると思われる.

まとめ

グラフ $G$ 上の 2 っのコータリを関連付ける G-支配という概念は, トポロジーが $G$ で表現されるネットワーク
上の相互排除システムの可用度と密接な関わりを持つ.
本稿で我々は, コータリボ G-支配される条件式を提示
し, それらの条件に基づいた 2 つのコーラム再割当アル
ゴリズム, Algorithm I と II, を提案した. これらのアルゴリズムはオリジナルよりも高い可用度を持つコータ
リを出力する. Algorithm II は Algorithm I より若干複雑となるが, 入力コータリがであれば, G-ND コー
タリが出力されることが保証される. また, トポロジー$\mathrm{N}\mathrm{D}$や入力コータリを変化させたいくつかの計算例により,

242

表 3: オリジナルと再割当後の可用度の比較 (ケース A)

表 4: オリジナルと再割当後の可用度の比較 (ケース B)

243
アルゴリズムの有効性を示した.
今後の課題としては, アルゴリズムの計算量の評価およびアルゴリズムの改善による計算量の低減が挙げら
れる.

参考文献
[1] D. Barbara and H. Garcia-Molina. The vulnerability of vote assignments. $ACM$ Trans. Computer
Systems, Vol. 4, No. 3, pp. 187-213, August 1986.

[2] D. Barbara and H. Garcia-Molina. The reliabilityof voting mechanisms. IEEE Trans. Computers,Vol. C-36, No. 10, pp. 1197-1208, October 1987.
[3] H. Garcia-Molina and D. Barbara. How to assign
votes in a distributed systems. J. $ACM$, Vol. 32,
No. 43, pp. 841-860, October 1985.
[4] T. Harada and M. Yamashita. Characterizing Gnondominated coteries on incomplete distributed
networks. In Proc. 10th Int. Conf. on Information
Networking, January 1996.
[5] T. Ibaraki, H. Nagamochi, and T. Kameda. Optimal coteries for rings and related networks. Distributed Computing, Vol. 8, pp. 191-201, 1995.

[6] M. Spasojevic and P. Berman. Voting as the optimal static pessimistic scheme for managing replicated data. IEEE Trans. Parallel and Distributed
Systems, Vol. 5, No. 1, pp. 64-73, January 1994.
[7] Z. Tong and. Kain. Vote assignments inweighted voting mechanisms. In Proc. 7th Symp.
Reliable Distributed Systems. IEEE, October 1988.
$\mathrm{R}.\mathrm{Y}$