数理解析研究所講究録
第 833 巻 1993 年 153-163

153

双方向リングネットワーク上での自己安定 2-相互排除
Self-Stabilizing 2-Mutual Exclusion on Bidirectional Rings
広島大学大学院工学研究科情報工学専攻
広島大学工学部第二類

角川裕次

山下雅史

(Hirotsugu Kakugawa)(Masafumi Yamashita)

Abstract-Self-stabilizing algorithms are algorithms that work correctly even if statesof processes are destroyed by errors; such algorithms can be considered as ideal fault tolerant algorithms. In this paper, we propose a uniform self-stabilizing 2-mutual exclusion
algorithm, i.e., an algorithm such that exact two processes have privileges in legitimate
configurations. The proposed algorithm works on bidirectional uniform ring networks
under cental deamon. It is uniform in the sense that every process executes the samealgorithm. We show that if , the number of processes in a network, is prime, then the
proposed algorithm correctly works. We also show that if is composite and is greaterthan or equal to 6, then there exists no algorithm for solving the problem.
$n$

$n$

1

はじめに

複数のプロセスより構成される、分散システムを考えよう。各プロセズは状態を持ち、隣接するプ
ロセス達から情報を集めながら状態を遷移してゆく。各プロセスの状態を組にしたものを、 システムの状況と呼ぶことにする。 ここで、「システムの初期状況に関わらず、 システムを正常な状況に遷移させる」 という問題を考える。 この問題は、一過性のエラーによってプロセスの状態が変わってし
まっても、再び (大域的な意味での) 正常な状況にもってゆこうとする問題と考えることができる。 このような性質を持つシステムは、「自己安定システム (self-stabilizing $system$ )」 と呼ばれ、耐故障性の観点から興味のあるシステムと考えられる。

この問題に対するトリビアルな解決策としては、 サーバープロセスを 1 つ用意し、 これが他のプロセスに対する指示を出すことによって再び正常な状況に遷移させるというものが考えられる。 しかし、 このためには、唯一の特別なプロセッサの存在や一意なプロセス識別子などを仮定する必要がある。 そこで、 同一のプロセスよりなるネッ トワークでの解が存在するか否かは興味ある問題である。

自己安定アルゴリズムは、近年活発な研究がなされてきている。 自己安定の概念は 1974 年 Dijkstra
によって提案された [1]、特別なプロセスが一つだけ存在するリングネットワークでの自己安定アル
ゴリズムが提案された。 [2] では、一様な (プロセス識別子がなく、全てのプロセスが同一のアルゴリ
ズムを実行する) 単方向リングネットワークにおいて、 プロセス数 $n\geq 2$ が素数なら自己安定 1-相互排除アルゴリズムが存在し、 が合成数ならば自己安定アルゴリズムが存在しないことが示されている。 また、 [3] では、 [2] で提案されたアルゴリズムのための、各プロセスが安定検出を行なうアルゴ
リズムを提案している。
本稿では、 個 ( は 3 以上の素数) の、 同一なプロセスより構成される双方向リングネットワークを考える。各プロセスは状態を持ち、 それ自身の状態と左右のプロセスの状態の上で定義された (幾っかの) 述語をもつ。述語が真の時、 そのプロセスは特権 (privilege) を持つといわれ、真である述語に対応した動作が可能である。 これまでは、正常な状態での特権の数が 1 である、 自己安定 1-相互排除アルゴリズムが提案されているが [2]、本稿では特権の数が 2 であるような自己安定 2-相互排除ア
ルゴリズムを提案し、 その正当性について示す。 また、 が 6 以上の合成数ならば、 アルゴリズムが存在しないことも示す。
$n$

$n$

$n$

$n$

154
自己安定 -相互排除問題

2$k$

それぞれの状態を,双方向リング上の連続した 個のプロセスをとする。 をプロセスの状態の有限集合とする。 システムの状況 (configuration) は、各プロセスの状態を組にしたもので、 $\gamma=(q_{0}, q_{1}, \ldots, q_{n-1})$ である。可能な状況の集合をとし、とあらわす。各プロセスのア’ ゴリズムは $((If$
正常な状況 (legitimate configuration) の集合をという (一般に複数個の) 規則で与える。 ここで $q,p,$ は、 それぞ$C(p, q, r)$ then $p\underline{q}rarrow F(p, q, r)$
れ、 リングでの左、それ自身、右のプロセスの状態を示す。ある状況\gamma \in F において、 プロセス が規則を適用して状況\gamma ’ になる時、と書く。 また、規則を適用するプロセス名が大切でない時は単にと書く。 更に、零回以上の規則の適用の連鎖の結果、状況が\gamma から\gamma ’ に遷移する時、と書く。
システム がself-stabihzing であるとは、次の条件を満たすことである:$n$$(q_{i}\in Q)$$p_{0},p_{1},$ $\ldots,p_{n-1\text{、}}$$q_{0},$ $q_{1},$$Q$$\ldots,$ $q_{n-1}$$\gamma$$\Gamma\subseteq Q^{n}$$A\subseteq\Gamma$

$r$

$i$

$\gammaarrow i\gamma’$$\gammaarrow^{*}\gamma’$$\gammaarrow\gamma’$$\Sigma$$k$

1. (No Deadlock) 任意の状況\gamma \in F に対し、少なくとも一つのプロセスが特権を持っ。
2. (Closure)$\forall\lambda,$$\lambda’(\lambda\in\Lambda, \lambda’\in\Gamma)[\lambdaarrow\lambda’\Rightarrow\lambda’\in\Lambda]$

3. (No Livelock) 任意の\gamma$\in\Gamma$に対しても、有限の遷移で正常な状況に達する。

4. (k-Mutual Exclusion) どの正常な状況においても、丁度 個のプロセスが特権を持つ。
$k$

5. (Faireness) 正常な状況を含む無限の遷移列において、 どのプロセッサも無限回特権を持っ。
一般に特権を持っプロセスは複数存在する。本稿では、 デーモン (central daemon) と呼ばれるモデルを取り扱う。 デーモンとは、特権を持っプロセスのうちどれか一っのみが選ばれ、対応した動作がアトミックに実行されるモデルである。 なお、特権を持ったプロセスは有限時間内に実行される、 という制約を付け加える。 (この制約がないと、 $k\geq 2$ に対して 相互排除アルゴリズムが存在しないことは容易に示すことが出来る。 )
$C$

$C$

$k$

3

自己安定 2-相互排除アルゴリズム

3.1

プロセス数が合成数の場合

補題 1 ある $a\geq 3$ に対し $n=2a$ のとき、 自己安定 2-相互排除アルゴリズムは存在しない。

(証明) 自己安定 2-相互排除アルゴリズムは存在すると仮定する。全てのプロセスの状態を任意のある状態 $q\in Q$ にした場合を考えると、仮定より全てのプロセスが特権を持っている。 プロセスを、長さが 2 のロセスを$a$個のブロックに分けて考える。各ブロック $i(1\leq i\leq a)$ での左のプロセスを $Pi$ ,l、右のプのとする。 $p_{1,1},p_{2,1},$で実行する。
,pj+l,l}ま一つのプロセッサを挟んで位置$p_{i,2}$$\ldots p_{a,1}$$||F$$p_{i,1}$

しているので、 $p_{i+1,1}$ の特権の有無は乃,1 の実行の影響を受けないことに注意せよ。

$a$個のプロセスの実行が終了した後は、 個もしくは $2a=n$ 個のプロセスが特権を持っ。次に、 もし $PI,2$ が特権を持っていれば、 $P1,2,P2,2,$ $\ldots Pa,2$ の順で実行する。先程と同様に、 個のプロセスの実行が終了した後は、個もしくは $2a=n$ 個のプロセスが特権を持つ。以降、上記の順で実行を無限に続ける。 このスケ
ジューリングにおいては、 $a\geq 3$ なので、有限時間内に特権の数は 2 にならない。 これは矛盾。 口
$a$

$a$

$a$

補題 2 ある 2 つの奇数 $a,$ $b\geq 3$ に対し $n=ab$ のとき、 自己安定 2-相互排除アルゴリズムは存在しない。

(証明) 本補題は補題 1 と同様な考え方で証明できる。長さ
せよ。

$b$

のブロックカ’$a$個存在することに注意口

155
定理 1 プロセス数 $n\geq 6$ が合成数のとき、 自己安定 2-相互排除アルゴリズムは存在しない。

(証明) 補題 1,2 より、本定理が成立。

口

プロセス数 $n=4$ に対して自己安定 2-相互排除アルゴリズムが存在するか否かは不明である。

3.2

プロセス数が 3 以下の場合

補題 3 プロセス数 $n=2$ に対する自己安定 2-相互排除アルゴリズムが存在する。
(証明) 明らか。
$n=3$ に対するアルゴリズムを以下に示す。 アルゴリズムの記法であるが、は、 プロセスの左、 それ自身、右の状態が各々 $p,$ $q,$$r$

$1f$ $C$口

then$p\underline{q}rarrow q’$’

であるとき、条件 $C$ が成立すれば、新しい状態

を $q’$ となることを表している。

The algorithm$S_{3}$

状態集合を $Q=\{0,1\}$ とする。各プロセス $P$ は次のアルゴリズムを実行する。 を $P$ の状態、 $a(c)$を $P$ の左プロセス (右プロセス) の状態である。 なお、
である。
$b$

$\overline{0}=1,$$\overline{1}=0$

Rule aIf $b\neq a\wedge b=c$ then$a\underline{b}c$

Rule

$b$

If $b\neq a\wedge a=c$ then$a\underline{b}c$

Rule$arrow\overline{b}$$arrow b$

If $a=b=c$ then$c$$a\underline{b}c$$arrow\overline{b}$は自己安定 2-相互排除アルゴリズムである。
(証明) 容易に示すことが出来るので、証明は省略する。 なお、正常な状況の集合は補題 4 アルゴリズム$S_{3}$$\Lambda_{3}=\{100,110,010,011,001,101\}$

である。

33

口

プロセス数 5 以上の素数に対するアルゴリズム

ここでは、 $n\geq 5$ に対するアルゴリズムを与え、 その正当性を証明する。 各プロセスの状態は 3 つ組 l.t.s で表す。 $l\in\{0,1, \ldots, n-3\}$ をラベル部、 $t\in\{0\}\cup\{2,3, \ldots, n-3\}$ をタグ部、 $s\in\{0,1\}$ を対称部と呼ぶ。 $buy$ を $P$ の状態、 a.t.x (c.v.z) を $P$ の左プロセス (右プロセス) の状態である。 なお、
タグ部及びラベル部に対する演算は、 $n-2$ を法として行なう。

システムが次の状況にある時が、正常な状況である。

. . . , $a-1.0.0$ , a.O.O,. . . , $a-1.0.0,$$a.0.0,\underline{a.0.*}’$$\underline{a.0.*},\underline{a.0.0},$$a+1.0.0,$$\ldots,$$a+1.0.0,$$b-1.0.0,$$\ldots$or,$b.0.0,\underline{b.0.1},$$b+1.0.0,$$\ldots$

但し、 は 0,1 任意のものとする。 なお、下線を引いた状態を持っプロセスが特権を持っている。 $n=7$$*$

に対する正常な状況の例を示す。

156$000,000,1002.00,200,300,400$
0.0.0,

3.4$\underline{0.0.1},$$\underline{0.0.0},1.0.0,2.0.0,3.0.0,4.0.0$

アルゴリズムThe algorithm$S_{n}$

for $n\geq 5$ :Rule AIf $b\neq a+1\wedge(b\neq 0\vee t=0\vee t=n-3\vee t\neq b-a\vee t<u)$$\wedge\neg(a=c=0\wedge b=n-3\wedge t=n-3)$$\wedge\neg(a=b=c=0\wedge t=n-3\wedge u=0)$$\wedge\neg(a=b=c\wedge x=0)$ then$a.t$

.xb.u.yc.v.z $arrow(a+1).(b-a).O$

Rule BIf $b=a+1\wedge t\neq u\wedge b\neq 0$ then$a.t$

.xb.u. ycvz $arrow$ b.t.yRule CIf $a=c=0\wedge b=n-3\wedge t=n-3$ then$a.t$

.xb.u.yc.v.z $arrow a.O.1$

Rule DIf $a=b=c\wedge x=0$ then$a.t.xb.u.yc.v.zarrow b.O.1$

3.5$\Gamma$

アルゴリズムの正当性を可能な状況の集合、 A を正常な状況の集合とする。 はじめに、本稿で用いる用語を定義する。

とす
定義 1 連続したプロセスを $p0,p_{1},$,Pn-l とし、 それぞれの状態のラベル部を$l_{k+1}=l_{k}+1(i\leq
k<j)$(segument)とは、連続したプロセスの列る。セグメントで、で、$l_{0},$$\ldots$$\ldots,$$p_{i},$

かっ $l_{i}\neq l_{i-1}+1,$ $l_{j+1}\neq l_{j}+1$ であるものをいう。

するとき、 $Pi$ を
$s$

$s$

$l_{i+1}-l_{i}$$s$$p_{i}(p_{i+1})$

を

$s$

$g$

部が

のギャップサイズであるとき、$s$[は well$\ldots,p_{j}$よりなるセグメントとのテイ $Js$ プロセス (s’ のヘッドプロセス) とすである。 ギャップサイズが であるギャップを ギャップ ($g$$p_{i},$のテイルプロセス (tail process) と呼ぶ。

と s’ の間にギャップ (gap) があるといい、 セグメント

が $n-3$ のとき $-1$ ギャップ ( $-1$ gap) いう。 セグメント
$s$

$s$

$l_{n-1}$$\ldots,p_{j}$を、 プロセス$s$のへッドプロセス (head process)、 $Pj$ を, s’ を 2 つの連続したセグメントとし、るとき、$l_{1},$$s$$s$のギャップサイズ (gap size) とは、

gap) といい、特にギャップ サイズ$\circ$$g$に属している全てのプロセスの状態のタグ

formed である、 という。

補題 5 (Closure)(証明) 任意のに対して、 Rule $B,$が適用できないことは明らか。以下の証明においては、対称部 (状態の第三要素) は省略して書く。
$\forall\lambda(\lambda\in\Lambda)[\lambdaarrow\lambda’,$$C$$\lambda\in\Lambda$$\bullet$場合 1:$\lambda’\in\Gamma\Rightarrow\lambda’\in\Lambda|$

状況が. . . , $a-1.0,$のとき。 (即ち、特権プロセスが隣合わない時。) 適用可能なものは、 Rule A のみである。適用前の状況を. . . , $a-1.0,$$a.0,\underline{a.0},$$a.O,\underline{a.0},$$a+1.0\ldots$$a+1.0,$.

$\ldots,$$b-1.0,$ $b.O,$ $b+1.0,\underline{b.0},$$\ldots$

157とすれば、適用後の状況は、.. . , $a-1.0,$ $a.0,$ $a+1.0,$ $a+1.0,$.

$\ldots$となる。実行を行なったプロセスの右のプロセスに特権が移る。 この状況は A に属している。
$a+1.0,$場合 2: 状況が.. . , $a-1.0.0,$のとき。 (即ち、特権プロセスが隣合うは Rule A による特権を時。) 左側 (右側) の特権プロセスを $P_{1}(P_{2})$ とする。 は Rule $D$$a.O,\underline{a.0},\underline{a.0},$$\ldots$$P_{1}$$P_{2}$、

持っている。 が実行されても、実行されると、$P_{1}$. . ., $a-1.0,$$a.0,\underline{a.0},$$P_{1}$の対称部が 1 になるだけで、他の状況は変わらない。巧が$a+1.0,$ $a+1.0,$$\ldots$となる。 この状況は A に属している。

口

補題 6 (2-Mutual Exclusion)[ において特権プロセスは 2 っのみ存在する。](証明) 以下の証明においては、対称部 (状態の第三要素) は省略して書く。
に対して、$\forall\lambda(\lambda\in\Lambda)$.

$\bullet$$\lambda$$\forall\lambda\in\Lambda$

場合 1:

状況が. . . , $a-1.0,$$a.O,\underline{a.0},$$a+1.O,$$\ldots$, $b-1.0,$ $b.O,$$\underline{b.0},$$\ldots$のとき。 (即ち、特権プロ

セスが隣合わない時。) このとき、 ちょうど 2 つのプロセスが Rule A による特権を持っていることは明らか。
場合 2:

状況が. .. , $a-1.0,$$a.O,\underline{a.0},\underline{a.0},$$a+1.0,$$\ldots$のとき。 (即ち、特権プロセスが隣合う時。)

このとき、 1 っのプロセスが Rule A による特権を、 それと異なる 1 っのプロセスが Rule $D$ による特権を持っていることは明らか。

口

補題 7 (Faimess) \foral \mbox{\boldmath $\lambda$}(\mbox{\boldmath $\lambda$}\in A)[\mbox{\boldmath $\lambda$}以降、 どのプロセスも無限回の特権を持つ。](証明) 任意のA において、 2 っのプロセスが特権を持ち、少なくとも一っのプロセスは Rule A
による特権を持っている。 C-Deamon に対する条件より、 Rule $D$ による特権を持っプロセスのみが実行されることはなく、有限時間内に Rule A による特権を持っプロセスが実行される。 Rule A が適
口用されると、特権は右のプロセスに移る。
$\lambda\in$

補題 8 (No Deadlock)[ において、少なくとも一っのプロセスは特権を持つ。]
ある(証明)において、 どのプロセスも特権を持たないと仮定する。 Rule C,D の条件が全プロ
セスで不成立なので、 Rule A の条件が不成立となるためには、$\forall\gamma(\gamma\in\Gamma)$$\gamma$$\gamma\in\Gamma$$(b=a+1)\vee(b=0\wedge t\neq 0\wedge t\neq n-3\wedge t=b-a\wedge t\geq u)$

V $(a=b=c=0\wedge t=n-3\wedge u=0)$

が全プロセスにおいて成立する。 プロセス数は , 状態のラベルは $0,1,$$n-3$ であることより、全てのプロセスで $b=a+1$ は成立し得ない。
同一のラベルを持つ連続したプロセスが 2 っ以上存在する場合を考える。
$n$$\bullet$$\ldots,$

全てのプロセスのラベル部が等しい場合。各プロセスのラベルが等しいので、全てのプロセスにおいて節 $a=b=c=0\wedge t=n-3\wedge u=0$ のみが真である。 $P$ を任意のプロセスとすると、 $P$ のタグは$0$

で、 $P$ の左隣のプロセス$P_{L}$$a=b=c=0\wedge t=n-3\wedge u=0$ が成立するので、のタグは $n-3$ である。

$P_{L}$

のタグ}ま

$0$

$P_{L}$においてもである。 これは矛盾。

158

.

$i+1,$
である場合。 をラベルとする連続するプロセ
その他、即ち、 ラベル部が $i-1,$$P$$P$
スで一番右のものをとする。 において、 $a=i,$ $b=i,$ $c=i+1$ である。すなわち、 $b\neq a+1$ ,$\neg(t\neq 0\wedge t=b-a),$ $\neg(a=b=c=0)$ である。 ゆえに、 $P$ では上の条件が成立せず、 矛盾。
$i,$$\ldots,$

$i,$

$i$

$\ldots$

故に、 同一のラベルを持つ連続したプロセスは 2 つ以上連続して存在しない。 よって、上の条件は、$(b=a+1)\vee(b=0\wedge t\neq 0\wedge t\neq n-3\wedge t=b-a\wedge t\geq u)$に等価である。
$\bullet$.

セグメント数が 1 の時。ギャップは 1 つしかないので、ギャップサイズは $b-a=n-3$である。 よって、 $t\neq n-3\wedge t=b-a$ は常に偽であり、矛盾。

場合 1:セグメント数が 2 の時。

場合 2:
$-$

セグメント長が 1 と $n-1$ のものよりなる時。 この時のラベル列は、 $0,0,1,$ $\ldots n-3,0$ となるが、 同一のラベルを持つプロセスが 3 つ連続しているので、 この場合は生じない。

.

$-$

その他の時。 以下の、場合 3 と同様に示せる。

セグメント数が 3 以上の時。 このとき、 どのセグメントも左端のプロセスのみがラベルとしてを持つ。 Rule が適用できないので、各セグメント内でのプロセスのタグは等しい。
$t\geq u$ なので、全てのプロセスは同一のタグを持つ。故に、 セグメントの長さはどれも等しい。
が素数であることより、各セグメントは長さが 1 である。すなわち、 どのプロセスも等しいラ

場合 3:

$B$

$0$

$n$

ベル $0$を持っ。 これは矛盾。

口以上の補題により、 self-stabilizing であるため条件のうちの 4 つが示された。以下で、残りの条件、No Livelock、 即ち、任意の初期状態および任意のスケジューリングに対しても、有限時間内に正常な状況に到達することを示す。
まず、 セグメント数が 2 以下である状況であれば、有限時間内に正常な状況に到達することを示す。
補題 9$\gamma\in\Gamma$

において、 セグメント数が $L$ とする。 このとき、 ギャップサイズの総和は、 $G_{L}=$$L-2(mod n-2)$ である。
(証明)$\gamma$において、連続したロセスのラベルをそれぞれ
グメント$G_{L}$$s_{i}$の長さを$l_{i}$$L$$H_{i},$

個のセグメントを$T_{i}$とする。

$s_{i}$とする。各 でのヘッド, テイルプのギャップサイズは、 $g_{i}=H_{i+1}-T_{i}$ である。各セ$s_{0},$ $s_{1},$と $s_{i-1}$$\ldots,$$S_{L-1}$$s_{i}$とすれば、 $T_{i}=H_{i}+l_{i}-1,$ $\sum_{i=0}^{L-1}l_{i}=n$ である。以上より、次式を得る。

$=$$\sum_{i=0}^{L-1}g_{i}(mod n-2)$$=$$\{\sum_{i=0}^{L-1}H_{i+1}-\sum_{i=0}^{L-1}T_{i}\}(mod n-2)$$=$$\{\sum_{i=0}^{L-1}H_{i+1}-\sum_{i=0}^{L-1}(H_{i}+l_{i}-1)\}(mod n-2)$$=$$\{-\sum_{i=0}^{L-1}l_{i}+\sum_{i=0}^{L-1}1\}(mod n-2)$$=$$\{-n+L\}(mod n-2)$$=$$\{L-2\}(mod n-2)$
口159
補題 10 任意の\gamma \in F に対して、 \gamma 以降 Rule のみが連続して無限回適用されない。
のみが連続して無限回適用されるとする。 \gamma での (連続した) セグメント数を(証明) \gamma 以降 Rule
$B$

$B$

とおく。仮定より、 プロセスの状態のラベル部は変わらない。すなわち、各セグメン
トを構成しているプロセスは永久に変化しない。 また、少なくとも -つのセグメント が存在して、に属しているプロセスが無限回 Ruleを適用する。 以下、 この について考える。
での時刻を、以下のように定める。 においては、時刻 とする。 時刻 $t\geq 0$ 以降、 のプロセス
が Ruleを適用した時を時亥# $t+1$ と定める。 (システム全体において Rule のみしか適用されな$s_{0},$ $s_{1},$$\ldots,$$s_{L-1}$

$s$

$B$

$s$

$s$

$s$

$0$

$\gamma$

$s$

$B$

$B$

いことと、 Rule $B$ の適用の結果はセグメントの外には影響を与えないことに注意せよ。)

$s$

を構成す

とし、時刻
るプロセスを、左から右に向かって、での乃の状態のタグ部をおく。 各時刻 での に対して、 ベクトル $V_{t}=(v_{1}^{t}, v_{2}^{t}, \ldots, v\})\in\{0,1\}^{l}$ を次のように定める。
$P_{1},$ $P_{2},$$t$$t(\geq 0)$$P_{l}$$\ldots,$$x_{i}^{t}$と$s$$v_{i}^{t}=\{\begin{array}{l}0ifx_{i-1}=x_{i}\vee i=01otherwise\end{array}$

すなわち、巧はセグメント内の各プロセスが Rule による特権を持っているか否かを表している。 このベクトルの比較は、辞書式順で行なう。時刻 において疏が Rule の適用を行なうと、 $v_{i}^{t+1}=0$に注意すれば、全ての $t\geq 0$ に対し、 $V_{t}>V_{t+1}$ である。 ベクトル $(0,0, \ldots, 0)$ が最小となる。
口が無限回適用されることに矛盾する。
の元なので、 Rule
$B$

$B$

$t$

$v_{i}^{t}=1$$B$

補題 11 状況\gamma 以降、 セグメント数が一定とする。有限時間内に、全てのセグメントが well formedとなる。
(証明) 任意のセグメントを一つ固定し、 とする。仮定より、有限時間内で のテイルプロセスのラベル部が となることは明らか。 このプロセスを $P$ とおく。明らかに、 $P$ は有限時間内に のヘッドはラベルプロセスとなる。 Ruleを越えてタグを使えないことに注意すれば、 はこのとき wellformed となっている。 セグメント数は有限なので、有限時間内に全てのセグメントが well formed と
口
なる。
$s$

$s$

$0$

$s$

$B$

$0$

$s$

補題 12 をセグメント数が 1 である任意の状況とする。任意のスケジューリングに対し、有限時間内のある時刻において Ruleが適用される。
$\gamma$$C$はラベル(証明) \gamma 以降 Ruleが適用されないと仮定する。 Ruleを越えてタグを伝えないので、永久に Rule のみが適用されることはない。即ち、 \gamma 以降のどの時点においても、有限時間内に Rule
$C$

$B$

$0$

$B$

A が適用される。 Rule A が適用される度に、セグメントのテイルプロセスのラベルは 1 増える。 よっが Rule A を実行してセグメントのテイルプロセスとなり、て、 ある時刻が存在して、 あるプロセス
$P$

かっ
$0$

のラベルが

$0$

のときは、 Rule

$B$

$P$

となる。 このとき、 $P$ のタグ部は、 $(n-4)-(n-3)=n-3$ である。 ラベルがは実行できないので、 $P$ のタグは次に Rule A を実行するまで変わらない。 そして、更にある時刻が存在して、 $P$ がそのセグメントのヘッドプロセスとなる。 このとき、全プロセスのタグは $n-3$ となる。 その後、有限時間内に、 $P$ のラベルが $n-3$ となり、 セグメントのヘッ ドプ
ロセスとなる。 (全プロセスのタグは $n-3$ であることに注意せよ。 ) このとき、 $P$ のみが特権を持っ口ており、 それは Ruleによるものである。 これは矛盾。
$C$を における
補題 13 関数 :を、なる写像とする。 ここで、
セグメント数 ( ギャップの数) とする。 また、 $N$ は自然数の集合 $\{0,1,2, \ldots\}$ である。任意の$f$$\Gamma\mapsto N$$f(\gamma)=L_{\gamma}+z_{\gamma}$$L_{\gamma}\geq 1(z_{\gamma}\geq 0)$$- 1$$\gamma$$\gamma\in\Gamma$に対し、 \gamma \rightarrow \gamma ’ なる全ての\gamma ’に対し、 $2\leq f(\gamma’)\leq f(\gamma)$ が成立。
(証明) 任意の\gamma に対し、であり、 $L_{\gamma}=1$ のときなので、 $f(\gamma)\geq 2$ が成立。
セグメント数または-1 ギャップの数が変化するのは、 Rule A でセグメントが消滅する場合もしく$\in\Gamma$$L_{\gamma}\geq 1$、$z_{\gamma}\geq 0$

は Rule $C$ でセグメント数が増加する場合である。

$z_{\gamma}=1$

160

.
.

Rule A により、セグメントが消滅する場合。セグメント数は 1 減少する。新たに得られたギャッ
プサイズが-1 であれば、 $f(\gamma)=f(\gamma’)$ が、 それ以外なら、 $f(\gamma)>f(\gamma’)$ が成立。

Rule でセグメントが増加する場合。 Rule
1 っ増加させるので、 $f(\gamma)=f(\gamma’)$ が成立。
$C$

$C$

は-1 ギャップを 1 っ減少させて、 セグメントを以上より、 本補題が成立。

補題 14

口

ラベ ル 部が $a-1,$ $a,$ $a,\underline{a+1,\ldots,}$$b-1,$ $b,$ $b,$ $b+1,$ $\ldots a-2$$0$、

すなわちセグメント数が 2 で、個以上を考える。無限にセグメントが存在し、 \gamma \rightarrow *\mbox{\boldmath $\lambda$}である。
数が 2 であるような任意のスケジューリングに対して、 ある(証明) 補題 11 により、有限時間内に 2 つのセグメントは well formed となる。 これは正常な状況でギャップサイズが共に$0$で、 タグ部、対称部は任意であるような$\gamma\in\Gamma$$\lambda\in\Lambda$ある。

口$a-1$ とし、 タグ部、
補題 15
において、 ラベル部がある に対して $a,$ $a+1,$ $a,$ $a+1,$ $a+2,$あるが存在し、 \gam a \rightar ow *\mbox{\boldmath $\lambda$}で対称部は任意とする。 このとき、任意のスケジューリングに対して、ある。
(証明) 補題 12 により、 \gamma 以降のある時点で Rule が適用される。 Rule が適用された直後での、 2っのギャップサイズはともに である。 また、 セグメント数が 2 でギャップサイズが共に のときは$\gamma\in\Gamma$$a$$\ldots,$$\lambda\in A$

$C$

$C$

$0$

$0$

Rule は適用されないので、補題 13 により、 \gamma 以降の全ての状況でのセグメント数は 2 以下である。
Rule をあるプロセス が適用した後、 の左右のプロセスが Rule A を適用するまでは、 は Rule
A の条件 $\neg(a=b=c=0\wedge t=n-3\wedge u=0)$ により、 Rule A を適用できない。 また、 の右ま
たは左のプロセスが Rule A を適用した後では、 $a=b=c$ の成立するプロセスの左のプロセスの状
態の対称部は必ず である。 (Rule A の実行にともない、対称部はとなる。 ) このときは、 Rule A
$C$

$P$

$C$

$P$

$P$

(

$P$

$0$

の条件

$0$

$\neg(a=b=c\wedge x=0)$

により、 セグメントの吸収は生じない。即ち、 セグメント数は永久に2 である。 補題 14 により、有限時間内に正常な状況に達する。

補題 16$\gamma\in\Gamma$

口において、 セグメント数が 2 で、 かつ 2 つのギャップサイズがともに$0$でないとする。

が存在し、 \gamma \rightarrow *\mbox{\boldmath $\lambda$}である。
(証明) 任意の\gamma を固定する。 において、次のような状況にあるとする。
このとき、 任意のスケジュールに対し、 ある$\lambda\in\Lambda$$\gamma$$H_{0},$$H_{0}+1,$ $\ldots,$ $T_{0},$ $H_{1},$ $H_{1}+1,$ $\ldots,T_{1}$ここで、 $H_{i}(T_{i})$ は、 セグメント$s_{i}$のヘッド (テイ $Ks$ ) プロセスのラベルである。 2 っのギャップサイ

ズを $g_{0}=H_{1}-T_{0}\neq 0,$ $g_{1}=H_{0}-T_{1}\neq 0$ とおく。補題 9 より、 $G_{2}=g0+g_{1}=0$$\bullet$$\bullet$。

$g_{0}\geq g_{1}$とする。

$g_{0}=n-3$ のとき。 $91=1$ となり、 セグメント数が 2 であることに矛盾。
$\lfloor(n-3)/2\rfloor\leq g0\leq n-4$のとき。 \gamma 以降セグメント数が変化しない限りは、 Rule

$C$

を適用でき

ないことは明らか。 \gamma 以降、 セグメント数が 2 のままであると仮定すると、 ある時刻において、

2 っのセグメントは well formed となり、 かっセグメント$s_{1}$のヘッドプロセス $P$ のラベル部が$0$となる。 このとき、 $P$ において、 次が成立する。 $\neg b\neq 0$ since $b=0,$ $\neg t\neq 0$ since $t=g_{0}\neq 0$ ,since $t=g_{0}\neq n-3,$ $\neg t\neq b-a$ since $t=g_{0}=b-a,$ $\neg t<u$ sinceも) 適用できず、 セグメント so のヘッドプロセスのみが特権をゆえに、 は Rule A を (Rule
持ち、 Rule A を適用してゆく。 そして有限時間内にセグメントが吸収され、 セグメント数が1 となり、矛盾。 したがって、 ある時刻にセグメント数が 1 となる。 このことと補題 15 より、本$\urcorner t=n-3$$P$$t=g_{0}\geq g_{1}=u_{\text{。}}$$B$$s_{0}$

補題が成立。

口161と任意のスケジューリングに対し、 システムは有補題 17 セグメント数が 2 以下である任意の\gamma
限時間内に正常な状況に達する。
(証明) においてセグメント数が 1 ならば、補題 15 により有限時間内に安定する。 \gamma 以降セグメント$\in\Gamma$$\gamma$

数が永久に 2 なら、補題 14 により有限時間内に安定する。 において、 セグメント数が 2 で、 ある口
時点でセグメント数が 1 となれば、補題 15 が適用できる。
$\gamma$

以下では、セグメント数が $L>2$ である任意の状況に対しても、有限時間内にセグメント数が $L-1$となり、 ゆえに、 有限時間内にセグメント数が 2 になることを示す。
補題 18 セグメント数 では livelock は生じない。
, Pn-l とする。 セグメント数が のままでの livelock が生じたと(証明) 個のプロセスを恥,仮定すると、 Rule B,C の条件部は全プロセスにおいて不成立である。 もし Rule A による特権しか存在しないとすれば、 Rule A が適用され、 セグメントが減少し、 矛盾。 あるプロセスが Rule A のみで、他のプロセスが Ruleのみで特権を持っているとすれば、有限時間内に Rule A が適用され、セグメントが減少し、矛盾。 ゆえに、 同一のプロセスで Rule A と $D$ の条件部が同時には成立し得ないことに注意すれば、 Rule A の条件部が成立するプロセスは存在せず、 Rule $D$ による特権のみしか存在しない。
$n$$P_{1},$$n$$n$$\ldots$$D$

Rule A の条件部が成立しないことより、任意の時刻において全プロセスで次が成立。
$(b=0\wedge t\neq 0\wedge t\neq n-3\wedge t=b-a\wedge t\geq u)$

V $(a=b=c=0\wedge t=n-3\wedge u=0)\vee(a=b=c\wedge x=0)$

ゆえに、全プロセスのラベル部は等しい。従って、 この条件は、全てのプロセスのラベル部が等しいという仮定のもとで $(x=0)\vee(t=n-3\wedge u=0)$ と等価である。 Rule $D$ を実行したプロセスの右隣のプロセス $P$ では、 Ruleの定義より、 $x=1\wedge t=0$ となり、上の条件は成立しない。 よって、
$P$ は
口
Rule A を適用し、 セグメント数が $n-1$ となる。
$D$

補題 19 ある時刻\mbox{\boldmath $\tau$}以降 Rule が適用されず、 かつセグメント数が 3 以上と仮定する。すると、 あ
る時亥|\downarrow t $>\tau$ が存在し、 時刻 でのセグメント数は減少する。
(証明) \mbox{\boldmath $\tau$}以降、 セグメント数は一定の $L\geq 3$ と仮定し、矛盾を導く。補題 18 より、 $L\leq n-1$ と仮定できる。補題 9 より、 ギャップサイズの総和は $G_{L}=L-2$ である。
個のセグメントをのヘッ ドプロセス (テイルプロセス) の$S_{L-1}$ とおく。 セグメント
ラベルを $H_{i}(T_{i})$ とおく。 のギャップサイズ gi}ま、 $g_{i}=H_{i+1}-T_{i}$ である。補題 11 により、 ある時刻が存在して、全セグメントが well formed となる。
Rule A の条件部を考えれば、各セグメントのヘッドプロセスでは任意の時点において次が成立する。
$C$

$t$

$L$

$s_{0},$$s_{1},$$\ldots,$$s_{i}$$s_{i}$$b\neq 0\vee t=0\vee t=n-3\vee t\neq b-a\vee t<u$セグメントが well formed なので、 $t=b-a$ であること、各ヘッドプロセスは無限にしばしば$0$をラベルとして持つこと及び、各セグメント内のプロセスのタグ部は永久に一定であることに注意すれば、 この条件は $t=0\vee t=n-3\vee t<u$ に等価である。
$\bullet$$\bullet$

全てのヘッドプロセスで $t=0$ の時。 $G_{L}=L-2$ に反するので、 これは生じない。

その他の時。全てのヘッドプロセスにおいて $t<u$ は生じないので、 あるセグメントのヘッドプロセスにおいて $t=n-3$ となる。 以下では、 $t=n-3$ の成立するプロセスをヘッ ドプロセ
スとするセグメントについて考える。
$s$

162

$s$

のヘッドプロセス $P$ が Rule A を適用する時、$s$は少なくとも 2 っのプロセスより成る。 (しかプロセスがないと、 Rule A の適用にともなって

$s$

$s$

に一つ

が消滅し、 セグメント数が減少する。) よって、次のような状況がある時点で生じる:. .. ’ $0.n-3.x,$ $n-3.u.y,O.u.z,$$\ldots$

ここで、 $n-3.u.y$ を状態として持っているのが $P$ である。 この状況では、 $P$ において Rule $C$ の条件部が成立し、 Rule A のそれは不成立となる。仮定により、 Ruleにの左隣または右隣のセグメントが消滅する。 これは矛盾。

$C$は適用されないので、有限時間内
口$s$と任意のスケジューリングに対して、有限時間内に全てのプロセスは Rule A
補題 20 任意の\gammaを適用する。
(証明) あると、 に対するあるスケジュールリングに対してあるプロセス $P$ が Rule A を適用
しないと仮定する。 Rule A は、実行にともなって特権を失い、 (もし可能なら) 右隣へ特権を移す働きをする。従って、仮定により、 $P$ が Rule A による特権をブロックしてしまうので、 Rule A は\gamma 以
降、高々有限回しか適用されない。最後に Rule A が適用された直後の状況を とおく。 (もし\gamma 以降が適用可能とする。) 明らかに、 以降は有限回しか Rule
Rule A が適用されない場合は、ではない。最後に Rule が適用された直後の状況を とおく。 (もし 以降 Rule が適用されない
以降は各プロセスの状態のラベル部は変わらないので、 Rule の適用
とする。)
場合は、
は有限回である。最後に Rule が適用された直後の状況を とおく。 (もし 以降 Rule が適用さ$\in\Gamma$$\gamma\in\Gamma$$\gamma$$\gamma_{1}$$\gamma_{1}=\gamma$$\gamma_{2}=\gamma_{1}$$\gamma_{2}$$\gamma_{3}$$C$$\gamma_{1}$$B$$\gamma_{2}$$B$

れない場合は、$C$$\gamma_{1}$$C$$\gamma_{3}=\gamma_{2}$$B$$\gamma_{2}$$\gamma_{3}$とする。)

におけるセグメントを$s_{1},$$s_{2},$$\ldots,$$s_{L}$

とおく。 ( $3\leq L\leq n-1$ と仮定できることに注意せよ。) 補題

8 により、少なくとも一っのプロセスは Rule による特権を持っている。 Rule の適用を行なっても特権の移動は生じないので、 もし Rule 以外で特権を持ち、かっ Rule で特権を持っていないようなプロセスが存在すると、 C-Daemon のスケジューリングに対する制約により、有限時間内にそれが実行される。故に、 以降任意の時点で、 どのプロセスにおいても Rule A,B, の条件部は不成立でをと他の Rule とが同時には成立し得ないことに注意せよ。) あるプロセスが Ruleある。 (Rule$b\neqa+1\wedge
t=0\wedgex=1$において適用したとする。 このプロセスの右隣プロセスをとすると、の条件部が不成立。故に、有限時間内にが成立するので、 Rule A の条件部が成立し、 かつ Rule
口は Rule A を適用することとなり、矛盾。
$D$

$D$

$D$

$D$

$C$

$\gamma_{3}$

$D$

$D$

$P_{R}$$P_{R}$$D$$P_{R}$

補題 21 関数 $f$ を、補題 13 の中で定義されたものとする。任意の\gamma \in r と任意のスケジューリングに$t\geq 0,$
対し、となる。
とする。 ある が存在し、(証明) もしそのような が存在しないと仮定すれば、 livelock が生じていることになる。補題 18,19 より、 セグメント数が一定のままでの livelock は生じない。 よって、 セグメントの消滅と生成が繰り返されるような livelock が生じる場合を考える。 このためには、補題 13 により、 セグメントの消滅に伴って得られるギャップが必ず-1 ギャップであり、 かつ、 Rule の適用が無限回繰り返される。 Ruleが無限回適用されると、 \gamma 以降の (有限時間内の) ある時刻において、 セグメントの消滅の結果得られるギャップサイズが-1 $(=n-3)$ でないものが存在することを示す。
$\gamma_{0}=\gamma$$\gamma_{t}arrow\gamma_{t+1},$$\tau$$f(\gamma_{\tau})<f(\gamma_{0})$$\tau$$C$$C$

補題 17 より、 セグメント数は任意の時刻において 3 以上と仮定できる。 どのプロセスも Rule A を
少なくとも一度適用した時刻以降を考える。 (補題 20 より、 そのような時刻が存在することに注意せよ。 ) あるプロセス $P$ が Ruleが適用されると、 1 つの-1 ギャップが消滅し、 2 っの ギャップが生じてセグメント数が 1 増える。 この時の状況は、$C$. . . , $0.n-3.x,$ $0.0.1,0.v.z$ , . . .

$0$

163
である。 どのプロセスも少なくとも一度は Rule A を適用したので、 $x=0$ であることに注意せよ。
$s_{-1},$, を、 それぞれ、 $P$ の左のセグメント、 $P$ のみからなるセグメント、 $P$ の右のセグメントとす$s_{0}$$s_{1}$る。 Rule A の定義より、$s_{-1}$または$s_{1}$が消滅しない限りは、$s_{0}$

は消滅しない。 ところが、$s_{-1}$

も$s_{1}$

も消滅し得ないことを示す。
$\bullet$との左のセグメントをとのギャップサイが消滅すると仮定する時。
とし、が消滅して得られるギャップサイズは、 $g=g_{1}+0-1=g_{1}-1$ である。
とおく。
$g_{1}=0$ 。しかし、 s-l}ま 2 つのギャップではさまれたセグメとなるためには、$g=-1=n-3$ントであるので、は、 Rule A の定義により、消滅し得ない。

ズを$g_{1}$$s_{-2}$$s_{-2}$$s_{-1}$$s_{-1}$$s_{-1}$$s_{-1}$$0$$s_{-1}$$\bullet$が消滅する時と同様に、 2 つのが消滅する時。
することになり、 Rule A の定義に矛盾。
$s_{1}$$s_{-1}$$0$

ギャップではさまれたセグメントが消滅

以上のことが Rule $C$ を適用して得られたセグメント全てに対して成立する。 よって、セグメントの吸収の結果得られたギャップサイズが-1 でないものが存在する。 この時刻を とすれば、$\tau$$f(\gamma_{\mathcal{T}})<f(\gamma_{0})$

である。

口

定理 2 プロセス数が $n\geq 2$ なる各素数に対し、 自己安定 2-相互排除アルゴリズムが存在する。

(証明) $n\geq 5$ なる素数の場合を考える。 Closure, 2-Mutual Exclusion, Fairness, No Deadlock はすでに示された。任意の\gamma \in r に対して、は有限なので、 これまでの一連の補題より、任意の状態から有限時間内でセグメント数が 2 以下となる。更に、 セグメント数が 2 以下である任意の状況から有限時間内で正常な状況に達することが示された。故に、 No Livelock が成立する。 よって、 $S$ は自口
己安定 2-相互排除アルゴリズムである。 このことと、補題 3,4 により、 本定理が成立する。
$f(\gamma)$4結論

本稿では、 プロセス数が 2 以上の素数であれば自己安定 2-相互排除アルゴリズムが存在し、 プロ
セス数が 6 以上の合成数であれば、 アルゴリズムが存在しないことを示した。 しかし、 プロセス数が$4=2\cdot 2$ の時にアルゴリズムが存在するか否かは未解決である。 本稿で用いた技法を拡張すること
でより一般的な自己安定た-相互排除アルゴリズムが構成できるものと思われ、 これは今後の課題で
ある。

参考文献
[1] E.W.Dijkstra. Self-Stabilizing Systems in Spite of Distributed Control. Communications of the$ACM,$ $17(11)$ , Nov. 1974, 643-644.
[2] J.E.Burns and J.Pachl. UniformSelf-Stabilizing Rings. A CM Trans. on Programming Languages
and Systems, 11 (2), Apr. 1989, 330-344.
[3] C.Lin and J.Simon. Observing Self-Stabilization. Proc. PODC, 113-123 (1992).
[4] J.L.W.Kessels. An Exercise in Proving Self-Stabilization with a Variant Function. Inform. Proc.
Lett., 39-42 (1988).