로차-테테 사이클 검출 알고리즘

Rocha-Thete 알고리즘은^[1] 대량 동기식 메시지 패스 추상화에 기반한 대규모 지시 그래프의 사이클을 검출하기 위한 그래프 이론의 분산 알고리즘이다.메시지 패싱에 의한 사이클 검출 알고리즘은 분산형 그래프 처리 시스템에서 구현하기에 적합하며, 주로 이차 메모리에 기반한 그래프치 등 디스크 기반 컴퓨팅을 위한 시스템에서의 구현에도 적합하다.^[2]디스크 기반 계산은 대규모 그래프를 처리하기 위해 하나의 컴퓨터를 가지고 있고, 그 계산이 기본 메모리 용량을 초과할 때 필요하다.

개요

Rocha-Thete 알고리즘은 대량 동기식 메시지 패스 추상화에 기초하여 정점들 사이에서 메시지를 전달함으로써$$ 지시된 $그래프{\displaystyle }$ G ${\displaystyle G}$의 사이클을 검출하기 위한 일반적인 알고리즘이다.이것은 그래프의 정점들이 사이클을 감지하기 위해 함께 작동하는 정점 중심 접근법이다.대량 동기 병렬 모델은 일련의 반복으로 구성되며, 각 반복에서 정점은 이전 반복에서 다른 정점에 의해 전송된 메시지를 수신하고 다른 정점에 메시지를 전송할 수 있다.

각 패스에서 $G{\displaystyle }$ ${\displaystyle G}$의 각 활성 꼭지점은 다음에 설명된 대로 정점 집합의 바깥쪽 근처로 전송된다$$.첫 번째 통과에서 각 $꼭지점{\displaystyle }$ v ${\displaystyle v}$이(가) 메시지$({\displaystyle v}$) ${\displaystyle(v)}$을(를) 모든 근거리 밖으로$$ 전송한다$$.이후 반복에서 각 활성 $정점{\displaystyle }$ v ${\displaystyle$ v$}$이(가) 이전 반복에서 받은 각 시퀀스에 $v$ ${\displaystyle v}$을(를) 추가한다$$.그런 다음 모든 업데이트된 시퀀스를 근거리 무선으로 전송한다.$v{\displaystyle }$ ${\displaystyle v}$이(가) 이전 반복에서 메시지를 수신하지 않은$$ 경우 $v{\displaystyle }$ ${\displaystyle v}$이(가) 자체 비활성화됨$$모든 정점이 비활성화되면 알고리즘이 종료된다.

$꼭지점{\displaystyle }$ v$${\$displaystyle$ v ${\displaystyle$v$}$이$(가)$ 수신한$$ 시퀀스$v$ ${\displaystyle {1\mathrm{}}_{}}$,$v$ ${\displaystyle {2\mathrm{}}_{}}$,${\displaystyle }$…${\displaystyle }$, ${\displaystyle v_{}}$ $k$) ${\$$displaystyle v$}의 경우, 추가된 시퀀스는 다음 두 가지 경우 전달되지 않는다$.$(i) if ${\displaystyle v=v_{1}}$, then ${\displaystyle v}$ has detected a cycle, which is reported; (ii) if ${\displaystyle v=v_{i}}$ for some ${\displaystyle i\in {2,3,\ldots ,k}}$, then ${\displaystyle v}$ has detected a sequence that contains the cycle ${\displaystyle (v=v_i}$${\displaystyle (v=v_{i},v_{i+1},\ldots ,v_{k},v_{k+1}=v)}$; in this case, the sequence is discarded, since the cycle must have been detected in an earlier iteration; to be precise, this cycle must have been detected in iteration ${\displaystyle k-i+1}$.Every cycle ${\displaystyle (v_{1},v_{2},\ldots ,v_{k},v_{k+1}=v_{1})}$ is detected by all ${\displaystyle v_{i},i=1}$ to ${\displaystyle k}$ in the same iteration; it is reported by the vertex ${\displaystyle \min\{v_$${1},\ldots,v_{k$

아래 그림은 알고리즘 실행의 예를 나타낸다.$반복$에서 ${\displaystyle \mathrm{i}}$= 3 ${\displaystyle$ i$=3$ 모든 정점 세 개가 사이클을 ${\displaystyle \mathrm{감지}}$한다$({\displaystyle }$2${\displaystyle ,}$ 3${\displaystyle ,4}$ ) ${\displaystyle(2,3,4).$ 알고리즘은 순서에서 최소 식별자 값을 가진 정점으로부터만 검출된 사이클을 방출하여 사이클이 단 한 번만 보고되도록 한다$.$^[1]

알고리즘의 총 반복 횟수는 그래프에서 가장 긴 경로에 있는 정점의 수에 최종 정점을 비활성화하기 위한 몇 단계를 더 추가한다.총 반복 횟수를 분석하는 동안 최종 정점을 비활성화하고 계산의 끝을 감지하는 데 필요한 몇 개의 추가 반복 횟수는 무시한다. 이는 $O{\displaystyle }$( ${\displaystyle 1}$) ${\displaystyle$ O$(1)}$ 반복이기$$ 때문이다.실제로 이러한 최종 몇 번의 반복의 실제 횟수는 알고리즘 구현에 사용되는 프레임워크에 따라 달라진다.^[1]

실험 성능

시뮬레이션에^[3] 따르면 Rocha-Thete 알고리즘은 메시지 수와 전송된 총 비트 수와 관련하여 깊이 우선 검색의 분산 버전보다 통신 오버헤드가 작다.구체적으로, DFS의 분산 버전은 Rocha-Thete 알고리즘보다 교환되는 최대 한 개의 더 많은 메시지를 요구할 수 있다.

참조