리더 선출

분산 컴퓨팅에서 리더 선출(leader election)이란 단일 프로세서를 여러 컴퓨터(노드)에 분산된 작업들의 주최자로 지정하는 작업이다. 작업이 시작하기 전, 모든 네트워크 노드들은 누가 작업의 "리더"로 동작할지 서로 알지 못하거나 현재 리더(분산 컴퓨팅)와 통신할 수 없다. 리더 선출 알고리즘 실행 후에는, 네트워크 상의 모든 노드들은 특별한 고유 노드를 작업 리더로 인식한다.

네트워크 노드들은 그들 중 누가 "리더" 상태가 될지 결정하기 위해 그들끼리 통신한다. 이를 위해, 그들은 그들간의 균형을 깨트리기 위한 방법이 필요하다. 예를 들어, 각 노드가 비교 가능한 고유 식별자를 가질 경우, 노드들은 그들의 식별자를 비교 가능하며, 가장 뛰어난 식별자를 가진 노드를 리더로 결정할 수 있다.

이 문제의 정의는 토큰이 손실된 링 네트워크에서 새로운 토큰을 만드는 방법을 정의한 LeLann으로부터 기인된다.

리더 선택 알고리즘은 총 전송 바이트, 시간 측면에서 경제적으로 설계된다. Gallager, Humblet 스파이라^[1]에 의해 제안된 무방향성 그래프를 위한 알고리즘은 분산 알고리즘의 설계에 큰 영향을 미쳤으며, 분산컴퓨팅 분야에서 영향력 있는 논문으로서 데이크스트라 상을 수상하기도 하였다.

다른 많은 알고리즘들이 다른 종류의 네트워크 그래프를 위해 제안되었다. (비방향성 링, 단방향성 링, 완전 그래프, 그리드, 방향성 오일러 그래프 등) 리더십 선거 알고리즘의 설계와 그래프 패밀리의 문제를 분리하는 일반적인 방법은 Korach, Kutten 및 Moran에 의해 제안되었다.^[2]

정의[편집]

리더 선출의 문제는 결국 각 프로세서가 리더인지 아닌지를 결정해야하며, 정확히 하나의 프로세서를 리더로 선정해야한다는 제약 사항이 있다.^[3] 다음 조건을 만족하는 경우 리더 선출 문제를 해결한 알고리즘이다 :

프로세서들의 상태가 선출됨과 선출되지 않음으로 나뉜다. 한번 선출되면 그것은 선출된 상태로 남는다.(선출되지 않은 경우도 마찬가지이다).
각 실행에서, 단 하나의 프로세서만 선출되고 나머지는 선출되지 않는다.

유효한 리더 선택 알고리즘은 다음과 같은 조건을 충족해야한다:^[4]

유한성 (Termination) : 알고리즘은 유한한 시간 안에 리더를 선출해야한다. 무작위 접근에선 이 조건은 때때로 약해진다. (예: 1의 확률로 종료를 요구하는 경우)
고유성 (Uniqueness): 정확히 하나의 프로세서가 리더로 고려되어야 한다.
일치화 (Agreement) : 모든 다른 프로세서들이 누가 리더인지 알아야한다.

다음과 같은 측면에서 리더 선출을 위한 알고리즘은 달라질 수 있다.^[5]

통신 원리: 프로세서는 클록 신호에 의해 프로세스가 동기화되는 동기식이거나 프로세스가 임의의 속도로 실행되는 비동기식일 수 있다.
프로세스 이름: 프로세스들은 독특한 식별자를 가질 수도 익명일 수도 있다.
네트워크 토폴로지: 링 네트워크, 유향 비순환 그래프 또는 완전 그래프.
네트워크 크기: 알고리즘은 시스템 내의 프로세스 개수 정보를 사용하지 않을 수도 있다.

참조[편집]

분산 컴퓨팅
깡패 알고리즘
Chang 및 로버츠 알고리즘
HS 알고리즘
투표 시스템

각주[편집]

↑ R. G. Gallager; P. A. Humblet; P. M. Spira (1983년 1월). “A Distributed Algorithm for Minimum-Weight Spanning Trees” (PDF). 《ACM Transactions on Programming Languages and Systems》 5 (1): 66–77. doi:10.1145/357195.357200. 2016년 10월 12일에 원본 문서 (PDF)에서 보존된 문서. 2018년 12월 3일에 확인함.
↑ Ephraim Korach; Shay Kutten; Shlomo Moran (1990). “A Modular Technique for the Design of Efficient Distributed Leader Finding Algorithms”. 《ACM Transactions on Programming Languages and Systems》 12 (1): 84–101. doi:10.1145/77606.77610.
↑ H. Attiya and J. Welch, Distributed Computing: Fundamentals, Simulations and Advance Topics, John Wiley & Sons inc., 2004, chap. 3
↑ I. Gupta, R. van Renesse, and K. P. Birman,2000, A Probabilistically Correct Leader Election Protocol for Large Groups, Technical Report , Cornell University
↑ R. Bakhshi, W. Fokkink, J. pang, and J. Van de Pol,c2008 "Leader Election in Anonymous Rings:Franklin Goes Probabilistic", TCS, Vol. 273, pp. 57-72.

[1] R. G. Gallager; P. A. Humblet; P. M. Spira (1983년 1월). “A Distributed Algorithm for Minimum-Weight Spanning Trees” (PDF). 《ACM Transactions on Programming Languages and Systems》 5 (1): 66–77. doi:10.1145/357195.357200. 2016년 10월 12일에 원본 문서 (PDF)에서 보존된 문서. 2018년 12월 3일에 확인함.

[2] Ephraim Korach; Shay Kutten; Shlomo Moran (1990). “A Modular Technique for the Design of Efficient Distributed Leader Finding Algorithms”. 《ACM Transactions on Programming Languages and Systems》 12 (1): 84–101. doi:10.1145/77606.77610.

[3] H. Attiya and J. Welch, Distributed Computing: Fundamentals, Simulations and Advance Topics, John Wiley & Sons inc., 2004, chap. 3

[4] I. Gupta, R. van Renesse, and K. P. Birman,2000, A Probabilistically Correct Leader Election Protocol for Large Groups, Technical Report , Cornell University

[5] R. Bakhshi, W. Fokkink, J. pang, and J. Van de Pol,c2008 "Leader Election in Anonymous Rings:Franklin Goes Probabilistic", TCS, Vol. 273, pp. 57-72.

[1]

[2]

[3]

[4]

[5]