10

彼の影響力のある論文、Self-stabilizing systems inにもかかわらず、分散制御を読みました。ただし、自己安定化アルゴリズムがどのように機能するかはよくわかりません。私が最も興味を持っているのは、彼の k ステート マシンの「ソリューション」です。紙の密度はかなり強烈で、あまり意味がありません。このアルゴリズムは平易な英語でどのように機能しますか?

4

3 に答える 3

10

簡単な英語で説明してみます...

最初に、Jean-Francois Corbett がコメントとして書いたリンクを見てください。

意味

（ウィキペディアより）

システムは、次の場合にのみ自己安定しています。

  • どのような状態から始めても、システムが最終的に正しい状態 (収束) に到達することが保証されています。
  • システムが正しい状態にあるとすれば、障害が発生しなければ正しい状態にとどまることが保証されます (閉鎖)。

表記法

セミナー用紙と同じ

自己安定化システム

彼の論文では、ダイクストラは自己安定システムを次のように定義しています。

N+1 個のノードを持つ円グラフを考えてみましょう。(0 から N+1 まで)

各ノードは異なる状態になる可能性があります。

各ノードは異なる権限を持つことができます。(たとえば、xS = xR は特権になる可能性があります)

各ステップで、1 つのノードに特権が存在する場合、特定のルールを適用します。

if privilege then "what to do" endif

正当な州

彼は、正当な状態を、特権が 1 つしかない状態であると定義しています。

結論

説明されているシステムに Dijkstra の論文のさまざまなルールを適用すると、自己安定システムが得られます。(定義参照)

つまり、n 個の特権が存在する任意の状態 (1 つのノードに複数の特権がある場合でも) から、限られた数の状態で 1 つの特権のみが存在する状態に到達し、この状態の後は正当な状態にとどまります。そして、正当な状態に到達することができます。

簡単な例で自分自身を試すことができます。

4 つの状態のソリューションの例

一番下のノードと一番上のノードだけを取ってみましょう:

starting point: (upT,xT) = (0,0) and
                (upB,xB) = (1,0)

state1: (upT,xT) = (0,0) and
        (upB,xB) = (1,1)
    only one privilege present on B => legitimate
state2: (upT,xT) = (0,1) and
        (upB,xB) = (1,1)
    only one privilege present on T => legitimate
state3: (upT,xT) = (0,1) and
        (upB,xB) = (1,0)
    only one privilege present on B => legitimate
state4: (upT,xT) = (0,0) and
        (upB,xB) = (1,0)
    only one privilege present on T => legitimate

ここに 3 つのノードの結果があります: 下部 (0) 中央 (1) 上部 (2): 2 つの特権から始めます (正当な状態ではなく、正当な状態になるとそこにとどまります):

{0: [True, False], 1: [False, False], 2: [False, True]}
privilege in bottom
privilege in top
================================
{0: [True, True], 1: [False, False], 2: [False, False]}
first privilege in middle
================================
{0: [True, True], 1: [True, True], 2: [False, False]}
privilege in top
================================
{0: [True, True], 1: [True, True], 2: [False, True]}
second privilege in middle
================================
{0: [True, True], 1: [False, True], 2: [False, True]}
privilege in bottom
================================
{0: [True, False], 1: [False, True], 2: [False, True]}
first privilege in middle
================================
{0: [True, False], 1: [True, False], 2: [False, True]}
privilege in top
================================
{0: [True, False], 1: [True, False], 2: [False, False]}
second privilege in middle
================================
{0: [True, False], 1: [False, False], 2: [False, False]}
privilege in bottom
... etc

これは、n ノードのシステムで 4 つの状態メソッドをテストするための小さな Python コードです (私は Python があまり得意ではないので、見苦しいかもしれません)。すべての正当な状態が見つかると停止します。

from copy import deepcopy
import random

n=int(raw_input("number of elements in the graph:"))-1
L=[]
D={}
D[0]=[True,random.choice([True,False])]
for i in range(1,n):
    D[i]=[random.choice([True,False]),random.choice([True,False])]
D[n]=[False,random.choice([True,False])]
L.append(D)

D1=deepcopy(D)

def nextStep(G):
    N=len(G)-1
    print G
    Temp=deepcopy(G)
    privilege=0
    if G[0][1] == G[1][1] and (not G[1][0]):
        Temp[0][1]=(not Temp[0][1])
        privilege+=1
        print "privilege in bottom"
    if G[N][1] != G[N-1][1]:
        Temp[N][1]=(not Temp[N][1])
        privilege+=1
        print "privilege in top"
    for i in range(1,N):
        if G[i][1] != G[i-1][1]:
            Temp[i][1]=(not Temp[i][1])
            Temp[i][0]=True
            print "first privilege in ", i
            privilege+=1
        if G[i][1] == G[i+1][1] and G[i][0] and (not G[i+1][0]):
            Temp[i][0]=False
            print "second privilege in ", i
            privilege+=1
    print "number of privilege used :", privilege
    print '================================'
    return Temp

D=nextStep(D)
while(not (D in L) ):
    L.append(D)
    D=nextStep(D)
于 2011-06-22T09:59:36.930 に答える
1

これは、戦闘でテストされた自己安定化ライブラリです (非常に非同期の設計を使用):

https://github.com/hpc/libcircle

ダイクストラの自己安定リングがこのライブラリにどのように組み込まれたか (ワーク キュー分割技術) の詳細については、http: //dl.acm.org/citation.cfm ?id=2389114 を参照してください。

この論文を読み進める気がない場合でも、コードにはかなり適切にコメントが付けられています。たとえば、https ://github.com/hpc/libcircle/blob/master/libcircle/token.c をご覧ください。

免責事項: 私は図書館と紙の著者です。

于 2012-02-09T16:40:09.243 に答える