Как работает самостабилизирующийся алгоритм Дейкстры? - PullRequest
10 голосов
/ 22 июня 2011

Я прочитал его основную статью, Самостабилизирующиеся системы, несмотря на распределенное управление .Однако я не совсем понимаю, как работает алгоритм самостабилизации.Меня больше всего интересует его «решение» k-состояний.Плотность бумаги довольно интенсивная, и я не могу понять это.Как работает этот алгоритм на простом английском языке?

Ответы [ 3 ]

10 голосов
/ 22 июня 2011

Я могу попытаться объяснить это простым английским языком ...

Сначала вы должны взглянуть на ссылку Жан-Франсуа Корбетт написал в качестве комментария.

Определение

(из Википедии)

Система самостабилизируется тогда и только тогда, когда:

  • Начиная с любого состояния, гарантируется, чтосистема в конечном итоге достигнет правильного состояния (конвергенция).
  • Учитывая, что система находится в правильном состоянии, она гарантированно останется в правильном состоянии при условии, что не произойдет сбой (закрытие).

Обозначения

То же, что на семинаре

Самостабилизирующаяся система

В своей работе Дейкстра определяет самостабилизирующую систему следующим образом:

Рассмотрим круговой граф с N + 1 узлами.(От 0 до N + 1)

Каждый узел может находиться в разных состояниях.

Каждый узел может иметь разные привилегии.(например, xS = xR может быть привилегией)

На каждом шаге, если на одном узле присутствует привилегия, мы будем применять определенное правило:

if privilege then "what to do" endif 

Законные состояния

Он определяет легитимное состояние как состояние, в котором присутствует только одна привилегия.

Заключение

Если вы примените различные правила в работе Дейкстры для описанной системы, вы получите самостабилизирующуюся систему.система.(см. определение.)

т.е. из любого состояния с 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, поэтому он может быть уродливым), чтобы проверить методы 4 состояний с системой из nузлов, он останавливается, когда вы найдете все законные состояния:

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)
1 голос
/ 09 февраля 2012

Вот проверенная в бою библиотека самостабилизации (с очень асинхронным дизайном):

https://github.com/hpc/libcircle

Дополнительную информацию о том, как самостабилизирующееся кольцо Дейкстры было включено в эту библиотеку (методы разделения очереди работ), можно найти по адресу: http://dl.acm.org/citation.cfm?id=2389114.

Код также достаточно хорошо прокомментирован, если вам не хочется работать с бумагой. Например, взгляните на: https://github.com/hpc/libcircle/blob/master/libcircle/token.c

Отказ от ответственности: я автор библиотеки и бумаги.

0 голосов
/ 19 сентября 2013

Для алгоритма самостабилизирующегося кольца Дейкстры вы можете разделить действия каждого неотличимого процесса на действия замыкания и действия сходимости.Действие выделенного процесса P0 - действия замыкания.Действия конвергенции не участвуют в непроизводственных циклах.Что касается замыкающих действий, включая действия P0, они могут образовывать только бесконечный цикл с одной циркулирующей привилегией.Если случается, что у вас есть более чем одна привилегия, то действия закрытия не могут обеспечить их циркуляцию.Другими словами, количество привилегий продолжает уменьшаться, когда они проходят через P0: выделенный процесс.

Следующие две публикации особенно интересны, помимо доказательства Дейкстры в 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

...