10

我读过他的开创性论文，尽管有分布式控制，但仍能自稳定系统。但是，我不太明白自稳定算法的工作原理。我对他的 k 状态机“解决方案”最感兴趣。纸张的密度非常高，我无法理解它。这个算法在简单的英语中是如何工作的？

4

3 回答 3

10

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

首先，您应该查看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代码（我不太擅长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)
于 2011-06-22T09:59:36.930 回答
1

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

https://github.com/hpc/libcircle

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

如果您不想通读这篇论文，代码也会得到很好的注释。例如看一下：https ://github.com/hpc/libcircle/blob/master/libcircle/token.c

免责声明：我是图书馆和论文的作者。

于 2012-02-09T16:40:09.243 回答
0

对于 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

于 2013-09-19T17:49:08.100 回答