algorithm - Dijkstra 的自稳定算法如何工作？

Question

我读过他的开创性论文，Self-stabilizing systems in spite of distributed control .但是，我不太了解自稳定算法的工作原理。我对他的 k 状态机“解决方案”最感兴趣。纸张的密度非常大，我无法理解它。这个算法如何用简单的英语工作？

Answer 1

我可以尝试用通俗易懂的英语来解释...

首先你应该看看 link Jean-Francois Corbett 作为评论写道。

定义

(来自维基百科)

A system is self-stabilizing if and only if:

• Starting from any state, it is guaranteed that the system will eventually reach a correct state (convergence).
• Given that the system is in a correct state, it is guaranteed to stay in a correct state, provided that no fault happens (closure).

符号

与研讨会论文中的相同

自稳定系统

Dijkstra 在他的论文中定义了一个自稳定系统如下:

考虑一个有 N+1 个节点的圆图。 (从0到N+1)

每个节点可以处于不同的状态。

每个节点可以有不同的权限。 (例如 xS = xR 可以是特权)

在每个步骤中，如果在一个节点中存在特权，我们将应用特定规则:

if privilege then "what to do" endif 

合法国家

他将合法状态定义为只有一种特权存在的状态。

结论

如果您对所描述的系统应用 Dijkstra 论文中的不同规则，您将获得一个自稳定系统。 (参见定义。)

即从任何具有 n 个特权的状态(即使一个节点具有多个特权)，您将在有限数量的状态中到达一个只有一个特权存在的状态，并在该状态之后保持合法状态。您将能够到达任何合法状态。

您可以尝试一个简单的例子。

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 个节点的结果:bottom (0) middle (1) top (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

这是一个小的 python 代码(我不是很擅长 python 所以它可能很难看)用 n 个节点的系统测试 4 种状态方法，当你找到所有合法状态时它停止:

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)