지도자 선거

분산 컴퓨팅에서 리더 선거는 단일 프로세스를 여러 대의 컴퓨터(노드) 사이에 분산된 일부 작업의 주관자로 지정하는 과정이다. 작업이 시작되기 전에 모든 네트워크 노드는 작업의 "리더"(또는 코디네이터) 역할을 할 노드를 인식하지 못하거나 현재 코디네이터와 통신할 수 없다. 그러나 지도자 선거 알고리즘이 실행된 후, 네트워크 전체의 각 노드는 태스크 리더로서 특정한 고유한 노드를 인식한다.

네트워크 노드는 그들 중 누가 "리더" 상태가 될 것인지를 결정하기 위해 그들끼리 의사소통을 한다. 그러기 위해서는 그들 사이의 대칭을 깨기 위해서는 어떤 방법이 필요하다. 예를 들어, 각 노드가 고유하고 비교 가능한 ID를 가지고 있다면, 노드들은 그들의 ID를 비교할 수 있고, 가장 높은 ID를 가진 노드가 리더라고 결정할 수 있다.

이 문제의 정의는 종종 LeLann에게 기인하는데, LeLann은 토큰이 분실된 토큰 링 네트워크에서 새로운 토큰을 생성하기 위한 방법으로 그것을 공식화했다.

리더 선거 알고리즘은 전송되는 총 바이트 수 및 시간 면에서 경제적이도록 설계된다. Gallager, Slevett, Spira가^[1] 일반 비방향 그래프를 위해 제시한 알고리즘은 일반적으로 분산 알고리즘 설계에 큰 영향을 미쳤으며, 분산 컴퓨팅 분야에서 영향력 있는 논문으로 Dijkstra상을 수상했다.

다른 종류의 네트워크 그래프에 대해 많은 다른 알고리즘이 제안되었다. 예를 들어, 비방향 링, 단방향 링, 전체 그래프, 그리드, 방향 오일러 그래프 등이 그것이다. 지도자의 선거 알고리즘 설계에서 그래프 계열의 문제를 분리하는 일반적인 방법은 코라크, 쿠텐, 모란이 제안했다.^[2]

정의

리더 선거의 문제는 각 프로세서가 리더인지 아닌지를 최종적으로 결정하는 것으로, 정확히 하나의 프로세서가 리더로 결정하는 제약에 따라 결정된다.^[3] 다음과 같은 경우에 알고리즘이 리더 선거 문제를 해결한다.

1. 프로세서의 상태는 선출된 상태와 선출되지 않은 상태로 나뉜다. 일단 선출되면 선출된 그대로 유지된다(유선되지 않더라도 유사하게).
2. 모든 실행에서 정확히 하나의 프로세서가 선출되고 나머지는 그들이 선출되지 않았다고 결정한다.

유효한 지도자 선거 알고리즘은 다음 조건을 충족해야 한다.^[4]

1. 종료: 알고리즘은 리더를 선택한 후 유한한 시간 내에 완료되어야 한다. 무작위화 접근방식에서 이 조건은 때때로 약화된다(예를 들어 확률 1로 종료를 요구한다).
2. 독특함: 자신을 리더로 간주하는 프로세서가 정확히 하나 있다.
3. 동의: 다른 모든 프로세서는 리더가 누구인지 안다.

지도자 선거를 위한 알고리즘은 다음과 같은 측면에서 달라질 수 있다.^[5]

• 통신 메커니즘: 프로세서는 프로세스가 클럭 신호에 의해 동기화되는 동기식 또는 프로세스가 임의 속도로 실행되는 비동기식이다.
• 프로세스 이름: 프로세스가 고유한 ID를 가지고 있는지 또는 구별할 수 없는지 여부(익명).
• 네트워크 토폴로지: 예를 들어 링, 순환 그래프 또는 전체 그래프.
• 네트워크의 크기: 알고리즘은 시스템의 프로세스 수에 대한 지식을 사용할 수도 있고 사용하지 않을 수도 있다.

알고리즘

링에서의 지도자 선거

링 네트워크는 각 노드가 두 개의 다른 노드에 정확히 연결되는 연결 그래프 위상이다. 즉, 노드가 n개인 그래프의 경우 노드를 연결하는 가장자리가 정확히 n개 있다. 링은 단방향일 수 있는데, 이는 프로세서가 한 방향으로만 통신한다는 것을 의미하며(노드는 메시지를 왼쪽으로만 송신하거나 오른쪽으로만 송신할 수 있음), 또는 양방향으로, 프로세서가 양방향으로 메시지를 송신하고 수신할 수 있다는 것을 의미한다(노드는 메시지를 왼쪽과 오른쪽으로 송신할 수 있음).

익명 반지

모든 프로세서가 동일하면 링은 익명이라고 한다. 좀 더 공식적으로, 시스템은 모든 프로세서에 대해 동일한 상태 기계를 가지고 있다.^[3] 네트워크의 크기가 프로세스에 알려진 경우에도 익명 링에서 리더를 선출하는 결정론적 알고리즘이 없다.^[3][6] 모든 과정이 같은 속도로 진행되면 익명의 링에서 대칭이 깨질 가능성이 없기 때문이다. 일부 단계 이후의 프로세서 상태는 인접 노드의 초기 상태에 따라서만 달라진다. 따라서 그들의 상태는 동일하고 동일한 절차를 실행하기 때문에 매 라운드에서 동일한 메시지가 각 프로세서에 의해 전송된다. 따라서 각 프로세서 상태도 동일하게 변경되며, 결과적으로 한 프로세서가 리더로 선택되면 다른 프로세서도 모두 변경된다.

단순성을 위해 익명의 동기 링으로 증명하십시오. 모순으로 증명하다. 크기가 n>1인 익명의 링 R을 고려하십시오. 이 익명 고리 R에 지도자 선거를 해결하기 위한 알고리즘 "A"가 존재한다고 가정하자.^[3]

보조정리: R에서 A의 허용 가능한 실행의 라운드$$ $k{\displaystyle }$ ${\displaystyle k}$ 이후, 모든 프로세스는 동일한 상태를 가진다.

$증거{\displaystyle }$. k ${\displaystyle k}$에 유도로 증명$.$

베이스 케이스: $k{\displaystyle }$= ${\displaystyle 0}$ ${\displaystyle k=0}$: 모든 공정이 초기 상태에 있으므로 모든 공정이 동일하다.

유도 가설: ${\displaystyle \mathrm{k}}$- 1 ${\displaystyle k-1}$ 라운드에$$ 대해 보조정리기가 참이라고 가정한다.

유도 단계: 원형 $k{\displaystyle }$ ${\displaystyle k}$에서 모든 프로세스는$$같은 메시지 $m{\displaystyle {}_{}}$ ${\displaystyle r_{}}$ ${\$을 오른쪽으로 보내고 동일한$$ $메시지{\displaystyle {}_{}}$ m ${\displaystyle l_{}}$ ${\$을(를) 왼쪽으로$$ 보낸다. 라운드 $k{\displaystyle }$- ${\displaystyle 1}$ ${\displaystyle k-1$ 이후 모든 프로세스가 동일한 상태에 있으므로 모든 프로세스는 왼쪽 ${\displaystyle {가장자리}_{}}$로부터 m $r{\displaystyle {}_{}}$ ${\$ 메시지를 수신하고 오른쪽 가장자리로부터$$ $m{\displaystyle {}_{}}$ ${\displaystyle l_{}}$ ${\$ 메시지를 수신한다. 모든 프로세스가 $라운드{\displaystyle }$ k ${\displaystyle k}$에서 동일한 메시지를 수신하고 있기 때문에, $라운드{\displaystyle }$k {\$displaystyle$ k$}$ 이후에 동일한 상태에 있다$.$

위의 보조정리기는 A의 시행에서 일부 한정된 횟수의 라운드를 거친 후, 한 프로세스는 선출된 상태로 들어가고 다른 프로세스는 선출되지 않은 상태로 들어간 사실과 모순된다.

무작위(확률적) 지도자 선거

익명의 링에서 지도자 선거의 문제를 해결하기 위한 일반적인 접근법은 확률론적 알고리즘의 사용이다. 그러한 접근법에서, 일반적으로 프로세서는 확률적 기능에 기초하여 일부 신원을 가정하고 그것을 네트워크의 나머지 부분에 전달한다. 마지막에 알고리즘의 적용을 통해 리더를 선택한다(확률이 높은).

비동기^[3] 링

(위에서 프로빙된) 익명 링에 대한 알고리즘이 없기 때문에, 비동기 링은 비동기식 익명 링으로 간주될 것이다. 익명이 아닌 링에서 각 프로세스에는 $고유$한 i ${\displaystyle d}$ ${\displaystyle id}$이$($가) 있으며, 링의 크기를 알지 못한다. 비동기식 링의 리더 선택은 O ($n{\displaystyle {2\mathrm{}}^{}}$) ${\displaystyle$O$(n^{2})$ 메시지$$ 또는 $O{\displaystyle }$(${\displaystyle n}$ ${\displaystyle \log \mathrm{logn}}$) ${\displaystyle O(n\log n)}$ 메시지를 사용하여$$ 일부 알고리즘으로 해결할 수 있다.

$O{\displaystyle }$( ${\displaystyle {}^{}}$ ${\displaystyle {2\mathrm{}}^{}}$) ${\displaystyle O(n^{2})$ 알고리즘에서$$ 모든 프로세스는 $i{\displaystyle }$ ${\displaystyle d}$ ${\displaystyle id}$이(가) 포함된 메시지를 왼쪽 가장자리로$$ 전송한다. 그런 다음 오른쪽 가장자리에서 메시지가 나타날 때까지 기다리십시오. 메시지의$$ $i{\displaystyle }$ ${\displaystyle d}$ ${\displaystyle id}$이(가$)$ 자체 $i{\displaystyle }$ ${\displaystyle d}$ ${\displaystyle id}$보다 크면 메시지를 왼쪽 가장자리에 전달하고, 그렇지 않으면 메시지를 무시하고 아무 작업도 수행하지 마십시오. $메시지$에서 ${\displaystyle i}$ d$${\$displaystyle id}$이(가) $자체{\displaystyle }$ ${\displaystyle i}$ d$${\$displaystyle id$과(와) 같다면, 내가 선출되었음을 알리는 메시지를 왼쪽으로 보낸다. 다른 과정들은 그 발표를 왼쪽으로 진척시키고 스스로 비선임자로 돌아선다. 이 알고리즘의$$ 상한은 $O{\displaystyle ({}^{}}$ ${\displaystyle {2\mathrm{}}^{}}$ )${\displaystyle O(n^{2})}$인 것이 분명하다.

$O{\displaystyle (n}$ ${\displaystyle \log }$ ${\displaystyle n}$) ${\displaystyle O(n\log n)}$ 알고리즘에서$$ 단계별로 실행 중이다. $k{\displaystyle }$ ${\displaystyle k}$단계에서$$ 왼쪽 ${\displaystyle {2k}^{}}$ ${\$과($와{\displaystyle {\mathrm{}}^{}}$) 오른쪽 ${\displaystyle {2k}^{}}$ ${\$ 가운데$$ 승자 여부를 결정하는 과정이 진행된다. 승자라면 다음 단계로 넘어갈 수 있다. $단계{\displaystyle \mathrm{}}$ 0$\{\backslash$$displaystyle 0}$에서 각 프로세스 $P{\displaystyle }$ ${\displaystyle P}$이(가) i $d{\displaystyle }$ ${\displaystyle id}$을(를) 사용하여 메시지를 왼쪽 및 오른쪽 이웃에$$ 전송하여 자신이 승자인지 여부를 결정해야 한다$$(이웃은 메시지를 전달하지 않음). The neighbor replies an ${\displaystyle ACK}$ only if the ${\displaystyle id}$ in the message is larger than the neighbor's ${\displaystyle id}$, else replies an ${\displaystyle ACK_{fault}}$. If ${\displaystyle P}$ receives two ${\displaystyle ACK}$s, one from the left, 오른쪽에서 $P{\displaystyle }$ ${\$$displaystyle$ $P}$이(가$)$ $0단계{\displaystyle \mathrm{}}$ {\$displaystyle 0$$}$에서 승자가 된다$$$.$ $단계{\displaystyle }$ k${\displaystyle }$- ${\displaystyle 1}$ ${\displaystyle k-1}$에서 승자는 $i{\displaystyle }$ ${\displaystyle d}$ ${\displaystyle$ $id$$}$을(를) 사용하여 메시지를 ${\displaystyle {2k}^{}}$ ${\$2$^{k}$에 보내야$$ 한다$$$.$$}}$ 올바른$$ 이웃들. 경로의 인접 네트워크가 ${\displaystyle i}$ d ${\displaystyle id}$보다 큰 $메시지$에서 i ${\displaystyle d}${\$displaystyle$ id$}$을(를) 수신하는 경우$,$ 메시지를 다음 인접 네트워크로 전달하고, 그렇지 $않으면{\displaystyle }$ A ${\displaystyle C}$ K ${\displaystyle {}_{}}$ ${\displaystyle a_{}}$ ${\displaystyle u_{}}$ l t$${\$displaystyle ACK_{fault$ ${\displaystyle {2k}^{}}$ ${\$${\displaystyle d}$ 표시 $스타일$ $2^{k}}}$을 수신하면 인접 네트워크로 응답하십시오$.$$tyle id}$ larger than its ${\displaystyle id}$, then sends back an ${\displaystyle ACK}$, otherwise replies an ${\displaystyle ACK_{fault}}$. If the process receives two ${\displaystyle ACK}$s, then it is the winner in phase ${\displaystyle k}$. In the last phase, the final winner 메시지에서$$ 자체 $i{\displaystyle }$ ${\displaystyle d}$ ${\displaystyle id}$을(를) 수신한 후 종료 메시지를 종료하고 다른 프로세스에 전송한다. 최악의 경우 각 단계에는 최대 $n{\displaystyle \frac{}{}}$ ${\displaystyle \frac{{2k}^{}}{}}$+ ${\displaystyle \frac{1}{}}$ ${\$ 당첨자가$$ 있으며, 여기서 $k{\displaystyle }$ ${\displaystyle k}$은 단계 번호다. $\lceil {\displaystyle }$ ${\displaystyle \log }$ ${\displaystyle }$(${\displaystyle \mathrm{n}}$-${\displaystyle }$1 ) ${\displaystyle \rceil }$ ${\displaystyle \lceil \log(n-1)\rceil$} 단계가$$ 모두 있다. 각 수상자는 각 단계에서 ${\displaystyle {2k}^{}}$ ${\$의 순서로 메시지를$$ 전송한다. 따라서 메시지 복잡성은 $O{\displaystyle (n}$ ${\displaystyle \log }$ ${\displaystyle n}$) ${\displaystyle O(n\log$ n$)}$ 입니다$.$

동기 링

아티야와 웰치의 분산 컴퓨팅 책에서 그들은 알려진 링 크기 $n{\displaystyle }$ ${\displaystyle$ n$}$을(를) 가진 동기 링에서 $O{\displaystyle }$(${\displaystyle n}$) ${\displaystyle O(n)}$ 메시지를$$ 사용하여 통일되지 않은 알고리즘을 설명했다$.$^[3] 알고리즘은 단계별로 작동하며, 각 $단계$에는 n ${\displaystyle$ n$}개$의 라운드가$$ 있으며, 각 라운드는 1개의 시간 단위가 있다. $단계{\displaystyle \mathrm{}}$ 0 ${\displaystyle 0}$에서$$${\displaystyle i}$ ${\displaystyle \mathrm{d}}$= 0 ${\displaystyle$ $id$$=0}$을(를$)$ 사용하는 프로세스가 있는 경우 프로세스 $0{\displaystyle \mathrm{}}$ ${\displaystyle$ 0$}$이(가) 다른 프로세스에 종료 메시지를 전송한다($종료$$$메시지 비용 n {\$displaystyle n}$ 라운드$$). 그렇지 않으면 다음 단계로 이동하십시오. 알고리즘은 프로세스 $i{\displaystyle }$ ${\displaystyle d}$ ${\displaystyle id$}과$($와) 같은 단계 번호가 있는지 확인한 다음$,$ $단계{\displaystyle \mathrm{}}$ 0 ${\displaystyle 0}$과(와) 같은 단계를 수행한다$.$ 실행이 끝나면 최소 i ${\displaystyle d}$ ${\displaysty id}$이(가) 리더로 선택된다$$. 정확히 $n개$의 ${\displaystyle n}$개의$$$$ 메시지와 $n{\displaystyle }$(${\displaystyle m}$ ${\displaystyle i}$ ${\displaystyle i}$ ${\displaystyle m}$ ${\displaystyle u}$ ${\displaystyle m}$ ${\displaystyle \mathrm{\_}}$ ${\displaystyle i}$ ${\displaystyle d}$+ ${\displaystyle 1}$) ${\displaystyle n(최소\_id+1$) 라운드를 사용했다.

이타이(Itai)와 로데(Rodeh^[7])는 공정이 동기화된 단방향 링에 대한 알고리즘을 도입했다. 그들은 링의 크기(노드 수)가 공정에 알려져 있다고 가정한다. 크기가 n인 링의 경우 a≤n 프로세서가 활성화된다. 각 프로세서는 a^(-1)의 확률로 후보가 될지를 결정한다. 각 단계가 끝나면 각 프로세서가 후보 c의 수를 계산하고, 1과 같을 경우 리더가 된다. c의 값을 결정하기 위해, 각 후보는 링 주위를 통과하는 단계의 시작에 토큰(페블)을 보내고, 정확히 n 시간 단위가 지난 후에 송신자에게 돌아온다. 모든 프로세서는 통과된 조약돌의 수를 세어 c를 결정한다. 이 알고리즘은 O(nlogn)의 예상 메시지 복잡성으로 리더 선출을 달성한다. 시스템의 교착상태를 감지하기 위해 타임아웃 메커니즘을 사용하는 경우에도 유사한 접근법이 사용된다.^[8] 프라임 사이즈와^[9][10] 홀수 사이즈와 같은 특별한 크기의 고리에 대한 알고리즘도 있다.^[11]

균일 알고리즘

대표 선거에 대한 일반적인 접근방식에서, 링의 크기는 과정에 알려져 있는 것으로 가정된다. 익명 고리의 경우 외부 실체를 사용하지 않고서는 지도자를 선출할 수 없다. 알고리즘이 존재한다고 가정하더라도 리더는 링의 크기를 추정할 수 없었다. 즉, 어떤 익명의 링에서, 알고리즘이 잘못된 링 크기를 계산하는 긍정적인 가능성이 있다.^[12] 이 문제를 극복하기 위해 피셔와 지앙은 각 프로세서가 고유한 리더가 있는지 물어볼 수 있는 이른바 리더 오라클 Ω?을 사용하였다. 그들은 어느 시점부터 같은 답을 모든 과정에 돌려줄 것이 보장된다는 것을 보여준다.^[13]

고유 ID가 있는 링

초기 작품 중 하나에서 장과 로버츠는^[14] ID가 가장 높은 프로세서를 리더로 선정하는 통일 알고리즘을 제안했다. 각 프로세서는 ID를 시계 방향으로 보낸다. 메시지를 수신하고 메시지를 자신의 메시지와 비교하는 프로세스. 더 크면 통과하고 그렇지 않으면 메시지를 폐기한다. 이 알고리즘은 평균 사례에서 최대$$ $O{\displaystyle }$ (${\displaystyle }$n ${\displaystyle {2\mathrm{}}^{}}$) ${\displaystyle$O$(n^{2})}$개의$$ 메시지와 $O{\displaystyle }$(${\displaystyle n}$ ${\displaystyle \log }$ ${\displaystyle n}$)$${\$displaystyle O(n\log n)}$을 사용한다는 것을 보여준다.
Hirschberg와 Sinclair는^[15] 프로세서가 양방향으로 메시지를 전송할 수 있도록 하는 2방향 메시지 전달 방식을 $도입$하여 O${\displaystyle }$(${\displaystyle n}$ log$){\displaystyle O(n\log$ n$)}$ 메시지$$ 복잡성으로 이 알고리즘을 개선했다.

망사 속의 지도자 선거

메쉬는 특히 병렬 시스템, 중복 메모리 시스템 및 상호연결 네트워크에서 네트워크 위상의 또 다른 인기 있는 형태다.^[16]
메쉬 구조에서, 노드는 코너(근접 두 개), 테두리(근접 세 개) 또는 내부(근접 네 개가 있음) 중 하나이다. x b 크기의 그물망에서 가장자리 수는 m=2ab-a-b이다.

방향성이 없는 망사

리더 선거를 지향적이지 않은 메시지로 해결하는 전형적인 알고리즘은 4개의 코너 노드 중 하나만 리더로 선출하는 것이다. 코너 노드는 다른 프로세스의 상태를 알지 못할 수 있으므로 알고리즘은 먼저 코너 노드를 깨워야 한다. 지도자는 다음과 같이 선출할 수 있다.^[17]

1. 웨이크업 프로세스: $k{\displaystyle }$ ${\displaystyle k}$ 노드가$$ 선택 프로세스를 시작하는 프로세스. 각 이니시에이터는 모든 인접 노드에 웨이크업 메시지를 보낸다. 노드가 이니시에이터가 아닌 경우 메시지를 다른 노드로 전달하기만 하면 된다. 이 단계에서는 최대 ${\displaystyle \mathrm{3n}}$+ ${\displaystyle k}$ ${\displaystyle 3n+k}$개의$$ 메시지가 전송된다.
2. 선거 과정: 외부 링에서의 선거는 최대 $6단계{\displaystyle \mathrm{}(+b}$)${\displaystyle }$- $(\displaystyle 6(a+b)-16}$개의$$ 메시지로 진행된다.
3. 종료: 리더가 모든 노드에 종료 메시지를 전송한다. 이것은 최대 2n개의 메시지를 필요로 한다.

메시지 복잡성은 최대 $6{\displaystyle \mathrm{}(+b}$)${\displaystyle }$- $(\displaystyle 6(a+b)-16$이며, 메쉬가 사각형인 경우 $O{\displaystyle (n)}$ ${\displaystyle$ O$({\sqrt{n})}$.

방향 메쉬

방향 메시(Oriented mesh)는 포트 번호가 나침반 레이블인 특별한 경우(예: 북쪽, 남쪽, 동쪽, 서쪽). 지향적인 메쉬에서의 지도자 선거는 사소한 것이다. "북쪽"과 "동쪽"과 같은 코너만 지정하면 돼 그리고 그 노드가 자신이 리더라는 것을 확실히 알 수 있도록 하면 돼

토러스

메쉬 아키텍처의 특별한 경우는 "wrap-around"와 메쉬인 토러스다. 이 구조에서 모든 노드는 정확히 4개의 연결 가장자리를 가진다. 그러한 구조에서 지도자를 선출하는 한 가지 접근법은 선거 단계라고 알려져 있다. 링 구조에서의 절차와 유사하게, 각 단계에서 이 방법은 결국 하나의 후보 노드가 남을 때까지 잠재적 후보자들을 제거한다. 이 노드가 리더가 된 후 다른 모든 프로세스의 종료에 대해 통지한다.^[16] 이 접근방식은 O(n)의 복잡성을 달성하기 위해 사용될 수 있다. 또한 네트워크에 결함이 있는 링크의 존재에 대처하기 위해 도입된 더 실용적인 접근법이 있다.^[18][19]

하이퍼큐브 선거

하이퍼큐브 $H{\displaystyle {}_{}}$ ${\displaystyle k_{}}$ ${\$은${\displaystyle (}$는) n =$2k$ {\$displaystyle$ n=2$^{k}$ 노드로$$ 구성된 네트워크로$$, 각각 $k{\displaystyle }$ = ${\displaystyle k}$ $및$ O(${\displaystyle n}$ log $){\displaystystystyle O(n)}$ 에지가$$ 있다. 이전과 유사한 선거단계를 통해 지도자 선거 문제를 해결할 수 있다. 각 스테이지에서는 두 개의 노드(결투 선수라고 불림)가 경합하고, 승자는 다음 스테이지로 승격한다. 이는 각 단계에서 결투자의 절반만이 다음 단계로 진입한다는 것을 의미한다. 이 절차는 단 한 명의 결투 선수만 남게 될 때까지 계속되며, 그것이 지도자가 된다. 선정되면 다른 모든 공정에 통보한다. 이 알고리즘에는 $O{\displaystyle (n}$) ${\displaystyle O(n)}$개의$$ 메시지가 필요하다. 지향적이지 않은 하이퍼큐브의 경우 유사한 접근법을 사용할 수 있지만${\displaystyle ,}$ $O{\displaystyle }$(${\displaystyle n}$ ${\displaystyle \log }$ ${\displaystyle }$ ${\displaystyle \log }$ ${\displaystyle n}$) ${\displaystyle O(n\log \log n)}$의 메시지 복잡성이 더 높다$.$^[16]

전체 네트워크에서의 선택

완전한 네트워크는 모든 프로세스가 서로 연결되는 구조, 즉 각 노드의 정도는 n-1이며 n은 네트워크의 크기가 된다. O(n) 메시지와 공간 복잡성을 가진 최적의 솔루션이 알려져 있다.^[20] 이 알고리즘에서 프로세스는 다음과 같은 상태를 가진다.

1. 더미: 리더 선거 알고리즘에 참여하지 않는 노드.
2. 수동적: 시작 전 프로세스의 초기 상태.
3. 후보: 웨이크업 후 노드 상태 후보 노드가 리더가 되는 것으로 간주될 것이다.

한 노드가 시스템의 총 노드 집합을 알 수는 없지만, 이 배열에서 모든 노드가 자신의 단일 후계자, 즉 인접 노드라고 하는 식별자를 알고,^[20] 모든 노드는 다른 노드에 의해 알 수 있어야 한다는 가정이 있다.^[21]

모든 프로세서는 처음에 깨어날 때까지 수동 상태에서 시작한다. 일단 노드가 깨어나면, 그들은 리더가 될 후보들이다. 우선 순위 체계에 따라 후보 노드는 가상 링에서 공동 작업한다. 어느 순간 후보자들은 링에서 앞서가는 후보들의 정체성을 알게 된다. 높은 우선순위 후보들은 하위 후보들에게 그들의 전임자들에 대해 묻는다. 우선순위가 낮은 후보들은 우선순위가 높은 후보들에게 답한 후 더미가 된다. 이 계획을 바탕으로, 최고 우선순위 후보는 결국 시스템의 모든 노드가 자신을 제외한 더미라는 것을 알고, 그 시점에서 그것이 리더라는 것을 안다.

위의 알고리즘은 사실이 아니며 다른 알고리즘으로 수정되었다.^[21]

보편적 지도자 선거 기법

이름이 암시하듯이, 이러한 알고리즘은 네트워크의 위상이나 그 규모와 같은 그 속성에 대한 사전 지식 없이 모든 형태의 프로세스 네트워크에 사용되도록 설계된다.^[16]

외치다

외침(프로토콜)은 일반 그래프에 스패닝 트리를 만들고 그 뿌리를 리더로 선택한다. 그 알고리즘은 가장자리 카디널리티에서 총비용 선형성을 가진다.

메가머거

본질적으로 이 기술은 나무의 뿌리가 리더가 되는 최소 스패닝 트리(MST)를 찾는 것과 비슷하다. 이 방법의 기본 개념은 개별 노드가 서로 합쳐져 더 큰 구조를 형성하는 것이다. 이 알고리즘의 결과는 나무(주기가 없는 그래프)로 루트가 전체 시스템의 리더인 것이다. 메가 머거 방법의 $비용$은 O${\displaystyle (m}$+ ${\displaystyle n}$ log${\displaystyle \mathrm{nn}}$) ${\displaystyle$ O$(m+n\log$ n$)}$이며 여기서$$ m은 에지 수, n은 노드 수입니다.

요요

요요(algorithm)는 사전 처리 단계와 일련의 반복이라는 두 부분으로 구성된 최소 소견 알고리즘이다.^[16] 첫 번째 단계 또는 설정에서, 각 노드는 모든 인접 노드와 ID를 교환하고, 그것이 그것의 입사 에지 방향을 정하는 값에 기초한다. 예를 들어, 노드 x의 ID가 y보다 작으면 x가 y를 향한다. 노드가 모든 인접 노드보다 작은 ID를 가지면 소스가 된다. 대조적으로, 모든 내부 가장자리(즉, ID가 모든 인접 영역보다 큰)를 가진 노드는 싱크대이다. 다른 모든 노드는 내부 노드.
모든 가장자리의 방향이 정해지면 반복 단계가 시작된다. 각 반복은 일부 후보가 탈락하는 선거 단계다. 각 반복에는 YO-와 –YO의 두 단계가 있다. 이 단계에서는 해당 싱크에 연결된 선원의 최소값을 각 싱크에 전파하는 프로세스를 시작한다.

요-

1. 소스(로컬 미니마)가 자신의 가치를 모든 근거리까지 전송
2. 내부 노드는 모든 근거리에서 값을 받기 위해 기다린다. 최소값을 계산해 근방에 보낸다.
3. 싱크(출발 에지가 없는 노드)는 모든 값을 수신하고 최소값을 계산한다.

-yo

1. 싱크대는 YES를 가장 작은 값을 본 이웃에게 보내고 NO를 다른 사람에게 보낸다.
2. 내부 노드는 가장 작은 값을 받은 모든 인접 네트워크로 YES를 전송하고 다른 노드에는 NO를 전송한다. NO를 1개만 받으면 NO를 모두에게 전송한다.
3. 출처는 모든 표를 받을 때까지 기다린다. 모두 찬성하면 살아남고, 찬성하지 않으면 더 이상 후보가 아니다.
4. 노드 x가 인접 y에 NO를 전송하면 해당 에지의 논리적 방향이 반대로 된다.
5. 노드 y가 근거리에서 NO를 수신하면 해당 링크의 방향이 뒤집힌다.

최종 단계 이후 NO를 받는 소스는 더 이상 소스가 아니며 싱크대가 된다. 추가 단계인 가지치기도 도입되어 쓸모없는 노드(즉, 노드 존재는 다음 반복에 영향을 미치지 않는다)를 제거한다.

1. 싱크대가 잎이면 쓸모없고 따라서 제거된다.
2. YO-단계에서 동일한 값이 둘 이상의 인접 네트워크로부터 노드에 의해 수신되는 경우, 한 노드를 제외한 모든 노드에 연결 링크를 제거하도록 요청한다.

이 방법은 총 O(mlogn) 메시지 비용이 든다. 가지치기를 포함한 그것의 진짜 메시지 복잡성은 공개적인 연구 문제로서 알려져 있지 않다.

적용들

본 섹션은 다음과 같은 예와 추가 인용문으로 확장할 필요가 있다. 추가하면 도움이 된다. (2014년 10월)

라디오 네트워크

라디오 네트워크 프로토콜에서 리더 선출은 종종 메시지 수집이나 방송과 같은 보다 진보된 통신 원리에 접근하기 위한 첫 단계로 사용된다.^[22] 무선 네트워크의 본질은 인접한 노드가 동시에 송신할 때 충돌을 유발한다; 리더를 선출하면 이 과정을 더 잘 조정할 수 있다. 네트워크의 직경 D는 리더를 선출하는 데 필요한 시간의 자연적인 하한인 반면, 리더 선거 문제에 대한 상한과 하한은 연구된 특정 라디오 모델에 따라 달라진다.

모델 및 런타임

무선 네트워크에서, n개의 노드는 모든 라운드에서 메시지를 송신하거나 수신하도록 선택할 수 있다. 충돌 감지를 사용할 수 없는 경우, 노드는 한 번에 둘 이상의 메시지를 수신하거나 침묵을 구별할 수 없다. 충돌 탐지를 사용할 수 있는 경우, 노드는 메시지 자체를 디코딩할 수 없더라도 동시에 두 개 이상의 수신 메시지를 탐지할 수 있다. 신호음 모델에서 노드는 통신사 감지를 통해 침묵 또는 적어도 하나의 메시지만 구별할 수 있다.

단일 홉 네트워크에 대해 알려진 런타임은 상수(충돌 감지 시 예상됨)부터 O(n log n) 라운드(결정론적 및 충돌 감지 없음)까지 다양하다. 멀티홉 네트워크에서 알려진 런타임은 대략 O(D+ log² n) 라운드(비핑 모델에서 높은 확률로), O(D log n) 라운드(비핑 모델에서 결정), O(n)(충돌 감지에서의 결정), O(n) 라운드^3/2(로그 로그 n)^0.5에서 O(결정론적이고 충돌 감지 없음) 라운드(결정론적 및 충돌 감지 없음)와 다르다.

참고 항목

• 분산 컴퓨팅#선거
• 괴롭힘 알고리즘
• 창과 로버츠 알고리즘
• HS 알고리즘
• 투표제

참조