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

Question

我已经阅读了他的开创性论文,即尽管采用分布式控制的自稳定系统.但是,我不太了解自稳定算法的工作原理.我对他对k状态机的"解决方案"最感兴趣.纸的密度非常强烈,我无法理解它.这个算法如何用简单的英语工作？

Answer 1

我可以尝试用简单的英语来解释它......

首先,你应该看看的链接让-弗朗索瓦·科贝特写在注释中.

定义

(来自维基百科)

当且仅当以下情况时,系统才能自我稳定:

• 从任何状态开始,保证系统最终将达到正确的状态(收敛).
• 鉴于系统处于正确状态,只要没有发生故障(闭合),就可以保证系统处于正确状态.

不缩

与研讨会论文中的相同

自稳定系统

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

考虑具有N + 1个节点的圆形图.(从0到N + 1)

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

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

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

if privilege then "what to do" endif 

合法国家

他将合法的州定义为只有一个特权的州.

结论

如果您在Dijkstra的论文中对所描述的系统应用不同的规则,您将获得一个自稳定系统.(cf定义.)

即,从任何具有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)