디크스트라-숄텐 알고리즘

Dijkstra-Scholten 알고리즘(Edsger W. Dijkstra 및 Carel S의 이름) 스콜텐)은 분산형 시스템에서 종료를 검출하기 위한 알고리즘이다.^[1][2]이 알고리즘은 1980년 디크스트라와 숄텐에 의해 제안되었다.^[3]

첫째, 트리인 단순 공정 그래프의 경우를 생각해 보십시오.나무 구조로 된 분산 연산은 흔하지 않다.이러한 공정 그래프는 계산이 엄격히 분할 및 재무 유형일 때 발생할 수 있다.노드는 계산을 시작하고 문제를 대략 같은 두 개(또는 그 이상, 보통 2의 배수)로 나누어 그 부품을 다른 프로세서에 분배한다.이 과정은 문제가 단일 프로세서에서 해결할 수 있을 만큼 충분히 작은 크기가 될 때까지 반복적으로 계속된다.

알고리즘.

Dijkstra-Scholten 알고리즘은 나무 기반 알고리즘으로, 다음과 같이 설명할 수 있다.

• 계산의 개시자는 트리의 루트다.
• 컴퓨터 메시지 수신 시:
  • 수신 프로세스가 현재 계산에 없는 경우: 프로세스는 메시지 발신인의 자녀가 되어 트리를 결합한다.(현재 수신확인 메시지는 전송되지 않음)
  • 수신 프로세스가 이미 계산 중인 경우: 프로세스는 즉시 메시지 발신인에게 수신 확인 메시지를 전송한다.
• 프로세스가 더 이상 자식을 갖지 않고 유휴 상태가 되었을 때 프로세스는 트리의 부모에게 확인 메시지를 보내 트리에서 스스로를 분리한다.
• 종료는 개시자가 자녀가 없고 유휴 상태가 되었을 때 발생한다.

트리용 디크스트라-숄텐 알고리즘

• 나무의 경우 종말을 감지하기 쉽다.잎 과정이 종료되었다고 판단되면, 그것은 부모에게 신호를 보낸다.일반적으로, 과정은 모든 아이들이 신호를 보내기를 기다렸다가 부모에게 신호를 보낸다.
• 그 프로그램은 루트가 모든 자식들로부터 신호를 받으면 종료된다.

Dijkstra-Scholten 알고리즘으로 지시된 반복 그래프

• 트리의 알고리즘은 반복적으로 지시된 그래프까지 확장될 수 있다.각 에지에 추가 정수 속성 결손을 추가한다.
• 수신 에지에서, 결손은 수신된 메시지 수와 회신에서 전송된 신호의 수 사이의 차이를 나타낼 것이다.
• 노드가 종료를 원할 때, 노드는 송신 에지로부터 신호를 수신하여 결손을 0으로 줄일 때까지 기다린다.
• 그런 다음 각 유입 에지에서 적자가 0이 되도록 충분한 신호를 보낸다.
• 그래프가 반복적이기 때문에 일부 노드에는 송신 에지가 없으며 이러한 노드는 수신 에지에 충분한 신호를 보낸 후 가장 먼저 종료된다.그 후에 상위 레벨의 노드는 레벨별로 종료된다.

반복 지시 그래프를 위한 Dijkstra-Scholten 알고리즘

• 사이클이 허용되면 이전 알고리즘이 작동하지 않는다.송신 에지가 0인 노드는 없을 수 있기 때문이다.따라서 잠재적으로 다른 노드와 상의하지 않고 종료할 수 있는 노드는 없다.
• Dijkstra-Scholten 알고리즘은 그래프의 스패닝 트리를 암묵적으로 생성함으로써 이 문제를 해결한다.스패닝 트리는 기본 그래프의 각 노드를 한 번 포함하는 트리이며, 에지 집합은 원래 에지 집합의 하위 집합이다.
• 트리는 소스 노드(연산을 시작하는)를 루트로 하여 지시(즉, 채널이 지시됨)된다.
• 스패닝 트리는 다음과 같은 방법으로 생성된다.변수 First_Edge가 각 노드에 추가된다.노드가 메시지를 처음 수신하면 메시지를 수신한 가장자리로 First_Edge를 초기화한다.First_Edge는 이후에는 절대 바뀌지 않는다.스패닝 트리는 고유하지 않으며 시스템의 메시지 순서에 따라 다르다는 점에 유의하십시오.
• 종료는 각 노드에서 3단계로 처리한다.
  1. 첫 번째 에지를 제외한 모든 수신 에지에서 신호를 전송한다. (각 노드는 각 수신 에지의 결손을 0으로 감소시키는 신호를 전송한다.)
  2. 모든 송신 에지에서 신호를 기다리십시오.(각 발신 에지에서 수신되는 신호의 수는 각각의 결함을 0으로 줄여야 한다.)
  3. First_Edge로 신호 전송(1단계와 2단계가 완료되면 노드가 스패닝 트리의 부모에게 종료 의도를 알린다.)

참고 항목

• 황의 알고리즘

참조