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

Question

我读过他的开创性论文，尽管采用分布式控制，但仍具有自稳定系统。然而，我不太明白自稳定算法是如何工作的。我对他的 k 状态机“解决方案”最感兴趣。纸张的密度相当大，我无法理解它的意义。这个算法用简单的英语来说是如何工作的？

Answer 1

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

首先你应该看看 链接< /a> 让-弗朗索瓦·科贝特 (Jean-Francois Corbett) 发表评论。

定义

（来自维基百科）

系统是自稳定的当且仅当：

• 从任何状态开始，都保证系统最终会达到正确的状态（收敛）。
• 鉴于系统处于正确状态，只要不发生故障（关闭），就保证保持正确状态。

符号

与研讨会论文中的相同

自稳定系统

在他的论文中，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 个节点的结果： 底部 (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

这是一个小的Python [<=2.7]代码（我不太擅长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)

Answer 2

这是一个经过实战测试的自稳定库（具有非常异步的设计）：

https://github.com/hpc/libcircle

有关如何将 Dijkstra 的自稳定环纳入此库（工作队列分割技术）的更多信息，请访问：http://dl.acm.org/itation.cfm?id=2389114。

如果您不想阅读本文，该代码也有很好的注释。例如，请查看： https://github.com/hpc /libcircle/blob/master/libcircle/token.c

免责声明：我是该库和论文的作者。

Answer 3

对于Dijkstra自稳定环算法，可以将每个不可区分过程的动作划分为闭合动作和收敛动作。特异进程P0的动作是关闭动作。收敛动作不参与非进展循环。对于包括P0在内的关闭动作，只能形成单个权限循环的死循环。如果碰巧您拥有多个特权，则关闭操作无法使它们保持循环。换句话说，当经过P0：杰出进程时，特权数量不断减少。

除了 Dijkstra 在 1986 年的证明之外，以下两篇出版物特别有趣：
1- http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.70.976&rep=rep1&type=pdf
2- http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.27.4320&rep=rep1&type=pdf