분산 최소 스패닝 트리

분산 최소 스패닝 트리(MST) 문제는 노드가 메시지 전달에 의해 통신하는 네트워크에서 분산 알고리즘에 의한 최소 스패닝 트리 구축과 관련이 있다.가장 기본적인 접근방식은 보르체프카의 알고리즘과 유사하지만, 고전적인 순차적 문제와는 근본적으로 다르다.이 문제의 한 가지 중요한 적용은 방송에 이용될 수 있는 나무를 찾는 것이다.특히, 메시지가 그래프의 가장자리를 통과하는 데 드는 비용이 유의하다면, MST는 소스 프로세스가 네트워크의 다른 모든 프로세스와 통신하는 데 드는 총 비용을 최소화할 수 있다.

이 문제는 1983년 갤러거 외 연구진에 의해 O${\displaystyle (V}$ ${\displaystyle \log v}$ V$){\displaystyle O(V\log$ V$)}$시간에$$ 처음 제안되어 해결되었다.^[1] 여기서 $V{\displaystyle }$ ${\displaystyle V}$은 그래프에서 정점 수입니다.이후 솔루션을 $O{\displaystyle (V}$) ${\디스플레이스타일 O(V)}($으$$^[2])로 개선하고 최종적으로^[3][4] $O{\displaystyle (V\sqrt{}}$ ${\displaystyle {\mathrm{로그}}^{}}$ ∗ ${\displaystyle {}^{}}$ ${\displaystyle V}$ +${\displaystyle D)}$ ${\디스플레이스타일$ O$({\sqrt{V}\log ^{*V+D)$로 개선했는데 여기서$$ D는 네트워크 또는 그래프 직경이다.솔루션의 시간 복잡성에 대한 하한은 결국 $\Omega {\displaystyle \mathrm{}}$(${\displaystyle V\frac{\sqrt{}}{}\frac{\log \log }{}}$ V${\displaystyle \frac{}{}}$+ ${\displaystyle D}$)으로 나타났다${\displaystyle .}$ ${\displaystyle \Oomega \left({\frac {\sqrt{V}}{\log V}}+D}\right$)로 나타났다^[5]$.$$}$

개요

입력 그래프 $G{\displaystyle (V}$ ${\displaystyle ,}$ E${\displaystyle }$) ${\displaystyle G(V,E)}$은 네트워크로 간주되며$$, 여기서 $꼭지점{\displaystyle }$ V$${\$displaystyle$ V$}$은 독립 컴퓨팅 노드, 가장자리 $E{\displaystyle }$ ${\displaysty E}$은 통신 링크다.링크는 고전적인 문제에서와 같이 가중치가 부여된다.

알고리즘을 시작할 때, 노드는 자신에게 연결된 링크의 무게만 알고 있다. (예를 들어, 이웃의 링크와 같이 더 많이 알고 있는 모델을 고려할 수 있다.)

알고리즘의 출력으로서, 모든 노드는 최소 스패닝 트리에 속하는 링크와 그렇지 않은 링크를 알고 있다.

메시지 전달 모델의 MST

메시지 전달 모델은 분산 컴퓨팅에서 가장 일반적으로 사용되는 모델 중 하나이다.이 모델에서는 각 공정이 그래프의 한 노드로 모델링된다.두 프로세스 간의 통신 채널은 그래프의 가장자리 입니다.

고전적 최소 신장 트리 문제에 일반적으로 사용되는 두 가지 알고리즘은 Prim의 알고리즘과 Kruskal의 알고리즘이다.그러나 분산 메시지 전달 모델에서는 이 두 가지 알고리즘을 적용하기 어렵다.주요 과제는 다음과 같다.

• Prim의 알고리즘과 Kruskal의 알고리즘 모두 한 번에 하나의 노드나 정점을 처리해야 하므로 병렬로 실행하기 어렵다.(예를 들어, Kruskal의 알고리즘은 에지를 차례대로 처리하여 이전에 선택한 모든 에지로 사이클을 형성할 것인지에 따라 MST에 에지를 포함시킬 것인지를 결정한다.)
• Prim의 알고리즘과 Kruskal의 알고리즘 모두 프로세스가 전체 그래프의 상태를 알도록 요구하는데, 이는 메시지 전달 모델에서 발견하기가 매우 어렵다.

이러한 어려움 때문에, 메시지 전달 모델에서 분산된 MST 알고리즘에 새로운 기법이 필요했다.어떤 것들은 고전 MST 문제에 대한 Borůvka의 알고리즘과 유사하다.

GHS 알고리즘

GHS 알고리즘인 Gallager, Slevett, Spira는 분산 컴퓨팅 이론에서 가장 잘 알려진 알고리즘 중 하나이다.이 알고리즘은 비동기 메시지 전달 모델에서 MST를 구성할 수 있다.

전제조건^[1]

• 알고리즘은 연결된 비방향 그래프에서 실행되어야 한다.
• 그래프는 각 가장자리에 할당된 구별되는 유한 가중치를 가져야 한다.(이 가정은 일관된 방식으로 가장자리 무게 사이의 관계를 끊음으로써 제거할 수 있다.)
• 각 노드는 처음에 해당 노드에 대한 각 에지 인시던트의 가중치를 알고 있다.
• 초기에는 각 노드가 대기 상태에 있고 그것은 자연적으로 깨어나거나 다른 노드로부터 어떤 메시지를 수신하여 깨어난다.
• 메시지는 가장자리 양방향으로 독립적으로 전송될 수 있으며 오류 없이 예측 불가능하지만 유한한 지연 후에 도착할 수 있다.
• 각 에지는 FIFO 순서로 메시지를 전달한다.

MST의 속성

MST T의 일부를 T의 하위 트리, 즉 T의 연결된 노드와 가장자리 세트로 정의한다.MST에는 두 가지 특성이 있다.

1. MST T의 파편이 주어진 경우 e를 파편의 최소 무게 나가는 가장자리가 되도록 한다.그런 다음 e와 인접한 비파괴 노드를 파편에 결합하면 MST의 또 다른 파편이 발생한다.^[1]
2. 연결된 그래프의 모든 가장자리가 서로 다른 가중치를 갖는 경우 그래프의 MST는 고유하다.^[1]

이 두 가지 속성은 GHS 알고리즘의 정확성을 증명하는 기초를 형성한다.일반적으로 GHS 알고리즘은 각각의 개별 노드를 파편으로 하고 새로운 파편을 형성하기 위해 일정한 방법으로 파편을 접합하는 것으로부터 시작된다는 점에서 상향 알고리즘이다.이 파편 결합 과정은 단 하나의 파편이 남아 있을 때까지 반복되며 속성 1과 2는 결과 파편이 MST임을 암시한다.

알고리즘 설명

GHS 알고리즘은 각 조각에 레벨을 할당하는데, 이것은 초기 값이 0인 비감소 정수다.0이 아닌 각 파편에는 파편이 생성될 때 선택되는 파편 내 코어 가장자리 ID인 ID가 있다.알고리즘을 실행하는 동안, 각 노드는 각각의 인시던트 에지를 세 가지 범주로 분류할 수 있다.^[1][6]

• 분기 가장자리는 MST의 일부로 이미 결정된 가장자리들이다.
• 거부된 가장자리는 MST의 일부가 아닌 것으로 이미 결정된 가장자리들이다.
• 기본 가장자리는 분기 가장자리도, 거부된 가장자리도 아니다.

레벨 0 조각의 경우 각 깨어난 노드는 다음을 수행한다.

1. 최소 가중치 입사 모서리를 선택하고 해당 모서리를 분기 모서리로 표시하십시오.
2. 다른 쪽의 노드에 알리려면 분기 모서리를 통해 메시지를 보내십시오.
3. 가장자리의 다른 쪽 끝에서 메시지를 기다리십시오.

이 장치가 연결하는 두 노드에 의해 선택된 가장자리는 레벨 1의 코어가 된다.

0이 아닌 레벨 파편의 경우 알고리즘 실행은 각 레벨에서 세 단계로 구분할 수 있다.

방송하다

핵심 브로드캐스트 메시지에 인접한 두 개의 노드는 조각의 나머지 노드에 전달된다.메시지는 분기 가장자리를 통해 전송되지만 코어를 통해 전송되지 않는다.각 방송 메시지에는 파편의 ID와 수준이 수록되어 있다.이 단계가 끝나면 각 노드는 새로운 조각 ID와 레벨을 받는다.

컨버지캐스트

이 단계에서는 파편의 모든 노드가 파편의 최소 무게 나가는 가장자리를 찾기 위해 협력한다.나가는 가장자리는 다른 조각에 연결되는 가장자리들이다.이 단계에서 보내는 메시지는 방송무대와는 정반대 방향이다.모든 리프(가지 가장자리가 하나만 있는 노드)에 의해 초기화되며 분기 가장자리를 통해 메시지가 전송된다.메시지에는 발견한 사건 송신 에지의 최소 가중치(또는 그러한 에지가 없는 경우 무한)가 포함되어 있다.최소 외향적 가장자리를 찾는 방법은 나중에 논의될 것이다.n-1 수렴캐스트 메시지를 수신한 후 각 비잎 노드에 대해(가지 가장자리 수를 n으로 한다) 메시지에서 최소 가중치를 선택하고 입사 발신 가장자리의 가중치와 비교한다.가장 작은 무게는 방송을 받은 지점 쪽으로 보내질 것이다.

코어 변경

이전 단계를 완료한 후 코어에 의해 연결된 두 개의 노드가 서로 수신한 가장 좋은 가장자리를 알릴 수 있다.그런 다음 그들은 전체 조각에서 최소 나가는 가장자리를 식별할 수 있다.메시지는 코어에서 분기 가장자리의 경로를 통해 최소 송신 가장자리로 전송된다.마지막으로 선택한 발신 에지를 통해 에지가 연결하는 두 조각의 결합을 요청하는 메시지가 전송된다.그 두 파편의 수준에 따라 두 파편 중 한 파편을 통합하여 새로운 파편을 형성한다(세부 정보는 아래에서 논의한다).

최소 중량 입사 발신 에지를 찾는 방법

위에서 논의한 바와 같이, 모든 노드는 코어로부터 브로드캐스트 메시지를 받은 후 최소 무게 나가는 인시던트 가장자리를 찾을 필요가 있다.노드 n이 방송을 수신하면 최소 무게의 기본 가장자리를 선택하고 파편의 ID와 레벨로 반대편의 노드 n'에 메시지를 보낸다.그런 다음 노드 n'은 가장자리가 송신 에지인지 여부를 결정하고 노드 n에 결과를 통지하는 메시지를 다시 전송한다.다음과 같이 결정한다.
사례 1: 파편_ID(n) = 조각_아이디(n')
그러면 노드 n과 n'은 동일한 파편에 속하게 된다(따라서 에지는 송신되지 않는다).
사례 2: 단편_ID(n) != 조각_ID(n')와 Level(n) <= Level(n)'.
그러면 노드 n과 n'은 서로 다른 조각(따라서 가장자리가 나가는)에 속한다.
사례 3: 파편_ID(n) != 조각_ID(n')와 Level(n) > Level(n')이다.
우리는 어떤 결론도 내릴 수 없다.이유는 두 노드가 이미 같은 파편에 속할 수 있지만 n노드는 방송 메시지 지연으로 인해 아직 이 사실을 발견하지 못했기 때문이다.이 경우 알고리즘은 노드 n'이 노드 n에서 받은 수준보다 높거나 같을 때까지 응답을 연기하도록 한다.

두 조각을 어떻게 결합하는 거지?

F와 F가 결합되어야 할 두 조각이 되게 하라.이를 위한 두 가지 방법이 있다.^[1][6]

• 병합: F와 F' 모두 공통 최소 중량 송신 에지와 레벨(F) = 레벨(F')을 공유할 경우 이 작업이 수행된다.결합된 조각의 레벨은 레벨(F) + 1이 될 것이다.
• 흡수 : 레벨(F) < 레벨(F)'일 경우 이 동작이 발생한다.결합된 파편은 F'와 같은 수준을 가질 것이다.

나아가 "흡수" 연산이 발생할 때 F는 코어를 바꾸는 단계인 반면 F'는 임의의 단계일 수 있다.따라서 "흡수" 작업은 F' 상태에 따라 다르게 수행될 수 있다.e는 F와 F가 결합하고자 하는 가장자리가 되고, n과 n은 각각 F와 F에서 e에 의해 연결된 두 개의 노드가 된다.고려해야 할 두 가지 경우가 있다.
사례 1: Node n'은 브로드캐스트 메시지를 받았으나, core로 다시 컨버전스 메시지를 보내지 않았다.
이 경우 단편 F는 단순히 F'의 방송 과정에 참여할 수 있다.구체적으로 'F'와 'F'가 이미 결합되어 새로운 'F'를 형성하고 있기 때문에 F'의 최소 무게 나가는 가장자리를 찾고자 한다.그러기 위해 node n'은 F에 있는 각 노드의 단편 ID를 업데이트하기 위해 F에 대한 브로드캐스트를 개시하고 F에 있는 최소 무게 나가는 에지를 수집할 수 있다.
사례 2: 노드 n'은 이미 수렴 메시지를 코어에 다시 보냈다.
node n'이 컨버전스캐스트 메시지를 보내기 전에, 최소 중량 송신 에지를 선택했어야 한다.위에서 논의한 바와 같이, n'은 최소 무게의 기본 가장자리를 선택하고, 선택된 가장자리의 반대편에 시험 메시지를 보내고, 응답을 기다리는 것으로 한다.e'가 선택된 가장자리라고 가정하면 다음과 같은 결론을 내릴 수 있다.

1. e’ != e
2. 중량(e') < 중량(e)

첫 번째 진술이 유지되면 두 번째 진술이 뒤따른다.첫 번째 문장의 경우, n'이 가장자리 e를 선택하고 가장자리 e를 통해 n에게 테스트 메시지를 보냈다고 가정합시다.그런 다음 노드 n은 응답을 지연시킨다("최소 중량 사고 송신 에지를 찾는 방법"의 사례 3에 따라).그렇다면 n'이 이미 수렴성 메시지를 보낸 것은 불가능하다.1과 2가 되면 e'는 F가 흡수된 후 보고할 최소 송신 에지이기 때문에 F를 F로 흡수하는 것이 안전하다는 결론을 내릴 수 있다.

최대 수준 수

위에서 언급했듯이, 파편은 "Merge" 또는 "흡수" 조작에 의해 결합된다."흡수" 작동은 모든 파편 중 최대 수준을 바꾸지 않는다."Merge" 작동은 최대 레벨을 1 증가시킬 수 있다.최악의 경우 모든 파편이 '머지' 작전과 결합돼 각 단계에서 파편 수가 절반가량 줄어든다.따라서 최대 레벨 수는 O${\displaystyle (}log{\displaystyle \log }$ ${\displaystyle V}$) ${\displaystyle O(\log$V)}이며$,$ 여기서 V는 노드 수입니다.

진행 속성

이 알고리즘은 가장 낮은 레벨의 파편에서 일부 조작은 차단될 수 있지만, 가장 낮은 레벨의 파편은 차단되지 않는 좋은 속성을 가지고 있다.이 속성은 알고리즘이 결국 최소 스패닝 트리로 종료됨을 의미한다.

근사 알고리즘

Maleq Khan과 Gopal Pandurangan에 의해 $O{\displaystyle (\log }$ ${\displaystyle n}$) ${\displaystyle$ O$(\log n)}$ - 대추출$$ 알고리즘이 개발되었다.^[7]이 알고리즘은 $O{\displaystyle (D}$+ ${\displaystyle L}$ ${\displaystyle \mathrm{로그}}$ ${\displaystyle n}$) ${\displaystyle O(D+L\log n)}$번으로$$ 실행되며, $여기$서 L ${\displaystyle L}$은 그래프의 로컬 최단 경로 직경이다^[7].

참조