요요(알고리즘)

Yo-Yo는 일반 연결 무방향 ^[1]^[2]그래프에서 최소 검색 및 리더 선택을 목적으로 하는 분산 알고리즘입니다.Mega-Merger와 달리, 그것은 사소한 종료와 비용 분석을 가지고 있다.

서론

요요는 니콜라 ^[3]산토로에 의해 소개되었다.그것은 연속적인 제거와 가지치기라고 불리는 그래프 축소 기술로 진행됩니다.알고리즘은 전처리 단계에서 분할되며, 그 후 "Yo-"라고 하는 순방향 단계와 "-Yo"라고 하는 역방향 단계의 순환 반복이 이어집니다.

전제 조건

Yo-Yo Builds는 다음과 같은 전제 하에 최소 리더를 선출합니다.

종합적인 신뢰성:송신중에 메세지가 손실되지 않는다.
초기 고유값(ID): 각 노드에는 고유 식별자가 있습니다.
양방향 통신 채널: 각 에지는 양방향이며, 양방향으로 통신이 가능합니다.

더 이상의 제한은 필요하지 않습니다.

알고리즘.

전처리

전처리 단계는 브로드캐스트와 함께 시작됩니다.웨이크업 상태에서 각 노드는 자신의 id를 모든 네이버에 전송하고 엣지를 고차 노드로 향하게 합니다.이는 논리적인 단계일 뿐이므로 절차에서 양방향 채널이 손실되는 일은 없습니다.컨버지캐스트에 의해 이니시에이터는 전처리 종료를 통지받습니다.이 프로세스에서는 다음 3가지 카테고리의 노드가 생성됩니다.

출처: 발신 노드가 있지만 수신 노드가 없는 노드.이것들은 각 동네의 최소 노드입니다.
중간 노드: 발신 및 수신 에지가 모두 있는 노드.이것들은 각 네이버의 최소 노드도 최대 노드도 아닙니다.
싱크: 들어오는 에지는 있지만 나가는 에지는 없습니다.이것들은 각 동네에서 가장 큰 노드입니다.

요...

위상은 소스 값이 싱크 쪽으로 내려갑니다.

"Yo-" 단계는 소스에 의해 시작됩니다.송신원은, 착신 에지를 개입시켜 ID 를 송신해, 대기합니다.중간 노드는 각 착신 에지로부터 각 ID를 수신할 때까지 대기합니다.모든 예상 값이 수집되면 최소 계산이 수행되고 최소 ID가 발신 에지를 통해 전송됩니다.이 단계에서는 싱크는 수동적입니다.

메시지는 방향 에지를 통해 전송되고 싱크대에 도달하여 "-Yo" 단계를 트리거합니다.

-요

-Yo 단계는 긍정/부정적 답변을 끌어냅니다.

싱크는 수신된 최소 ID를 계산하고 들어오는 에지를 통해 양의 YES 또는 음의 NO를 전송함으로써 "-Yo" 단계를 시작합니다.YES는 최소 계산 ID를 전달하고 나머지 에지를 통해 NO를 전달합니다.메시지는 구조에서 송신원으로 이동합니다.적어도 1개의 착신 NO를 가진 송신원은 데드 상태가 되어 후보 상태가 상실됩니다.

"Yo" 단계는 또한 비후보 소스에 소스-중간-싱크가 수용되는 재구성 단계를 포함한다.NO를 수반하는 에지는 반전되어 현재 스테이지의 패자 후보는 싱크 노드 또는 중간 노드가 됩니다.

가지치기

프루닝은 "-Yo" 단계에서 적용되는 최적화 기술로, 그 메시지는 보통 긍정/부정 응답과 통합됩니다.불필요한 에지 및 노드를 삭제합니다.전자는 $u>1$ > $u>1$ 1 {\ $displaystyle u$ > $u>1$ 1 {\displaystyle u} 인입 $u>1$ 에지로부터 $u>1$ 한 값을 받는 에지입니다. 거의 $3가지$ u {\ $displaystyle$ u}는 $u$ 노드에 의해 사용되지 않고 잘립니다.이러한 에지는 데드 상태가 되며 다음 반복에서는 무시됩니다.대신 후자는 v = 1 {displaystyle v $=$ 수신 $v=1$ $v=1$ 로 $싱크되는$ 단항 $싱크를 삭제$ 하여 노드 수를 줄입니다.이러한 에지는 수신된 최소값(유일한)을 YES 응답과 함께 강제로 반송하므로 최소 소견에 유용한 계산을 수행하지 않습니다.

프루닝 전후의 구조.먼저 가장 오른쪽 상단 노드가 NO를 수신하여 싱크대가 됩니다. 들어오는 가장자리가 하나만 있는 싱크대이기 때문에 노드가 트리밍됩니다.부모 및 중앙 지점도 마찬가지입니다.

비용.

전처리 단계는 에지에 입사하는 두 노드의 각 에지를 통한 교환으로 구성됩니다.따라서 비용은 $\sum _{v\in V}deg(v)=2m$ v $\sum _{v\in V}deg(v)=2m$ $\sum _{v\in V}deg(v)=2m$ $\sum _{v\in V}deg(v)=2m$ $\sum _{v\in V}deg(v)=2m$ ( $\sum _{v\in V}deg(v)=2m$ v ) $\sum _{v\in V}deg(v)=2m$ m \ $displaystyle$ \ $sum _$ { v \ $in$ V } $deg$ ( v ) $=$ 2 m $\sum _{v\in V}deg(v)=2m$ 。Yo-Yo 단계는 구조의 전방 및 후방 스캔으로 구성됩니다. $2m_{i}$ $2m_{i}$ $(\$ }) 메시지는 $2m_{i}$ $m_{i}$ 서 $(\$ })는 $m_{i}$ 현재 활성 에지의 수입니다.반복 횟수는 각 초기 소스를 삭제하는 데 유용한 반복 횟수로 지정됩니다.가설에 따라 각 소스는 중간 노드에 의해 적어도 다른 소스와 연결된다. 그렇지 않은 경우 그래프의 분리된 구성요소는 연결되지만, 정의상 그래프는 연결된다.최악의 경우 $n_{i}$ 의 $n_{i}$ 노드(\ $displaystyle n_{i})$ 가 $n_{i}$ 쌍으로 연결되며 각 반복에서 소스의 절반 이상이 제거됩니다. $n_{i+1}$ 각 $n_{i+1}$ + 1({ $displaystyle n_{i+$ 1}) 소스를 $n_{i+1}$ 재구성하면 이제 쌍으로 연결됩니다.이전 사례와 마찬가지로 절반만 살아남는다.1개의 소스만 남아 있을 경우 종료가 충족됩니다.절반으로 나누면 $log_{2}n$ 계산, 즉 $diam(G)$ $diam(G)$ m ( $diam(G)$ ) \ $display$ style $diam ( G$ ) $diam(G)$ $log_{2}n$ sources2 $log_{2}n$ \ $displaystyle log$ _ {2 $}$ $n$ } $log_{2}n$ 반복됩니다.총비용은 $2m\log {n}$ log $(\$ 입니다.

종료

스위치는 YES/NO 풀로 실행되는 방향으로 종료를 보증합니다."Yo" 단계의 소스 감소는 단조롭다. 즉, 이전의 관찰에 의해 각 소스를 적어도 하나의 다른 소스와 비교하고, 소스 고유성에 의해 이들 중 하나가 우세하며, 다른 하나는 소멸한다.초기 선원의 수는 한정되어 있기 때문에, 단조로운 감소는 단일 선원의 잔량으로 이어집니다.

레퍼런스

^ Gallager, Robert (1983). "A distributed algorithm for minimum spanning tree" (PDF). Massachusetts Institute of Technology.
^ Awerbuch, Baruch (1987). "Optimal Distributed Algorithm for Minimum Weight Spanning Tree, Counting, Leader Election and Other Problems" (PDF). SIAM Journal on Computing.
^ Santoro, Nicola. "Design and Analysis of Distributed Algorithms". people.scs.carleton.ca. p. 213. Retrieved 2017-03-13.

[1] Gallager, Robert (1983). "A distributed algorithm for minimum spanning tree" (PDF). Massachusetts Institute of Technology.

[2] Awerbuch, Baruch (1987). "Optimal Distributed Algorithm for Minimum Weight Spanning Tree, Counting, Leader Election and Other Problems" (PDF). SIAM Journal on Computing.

[3] Santoro, Nicola. "Design and Analysis of Distributed Algorithms". people.scs.carleton.ca. p. 213. Retrieved 2017-03-13.

[1]

[2]

[3]

Search