[CS] 분산 시스템에서의 리더 선출 알고리즘

선출 알고리즘 (Election Algorithms)

여러 노드 중에서 한 노드를 리더 또는 Coordinator(코디네이터)로 선택하는 역할을 수행한다. 이러한 알고리즘은 분산 시스템에서의 리더 노드를 동적으로 정하는 데 사용되며, 안정성과 효율성을 유지하는 데 중요하다.

 

분산 시스템에서는 여러 노드가 동시에 동작하며, 리더는 전체 시스템에서 특정 임무를 담당하거나, 특정 동작을 조정하며, 일관성을 유지하거나 효율적인 리소스 할당을 수행하는 역할을 수행한다. 여러 노드 중 하나의 노드를 리더로 선택하는 것은 중요한 과정이다.

 

 

1. Centralized Model → Coordinator Process의 Fail 시 새로운 Coordinator을 Election하는 과정을 거침

2. 각 활성 프로세스가 고유한 Priority ID(우선순위 ID)를 가진다고 생각함

3. 동적으로 실행됨

 

 

The Bully Algorithm

 

 

 

1. 한 프로세스가 Coordinator가 응답하지 않으면 Election을 더 높은 ID의 프로세스들에게 보낸다.
2. 상위 프로세스가 응답한다면 그 프로세스가 Election을 인계받는다.
3. 더 이상 응답하는 상위 프로세스가 없다면 승리자가 되어 Coordinator가 된다.

 

 

 

 

A Ring Algorithm

 

 

1. 프로세스 P는 프로세스 ID가 포함된 메시지를 다음 Avaliable한 프로세스에 보낸다.
2. 각각의 활성 프로세스에서 수신 프로세스에 ID를 추가하고, 후속 프로세스로 전달한다.
3. 결국 메세지는 Sender에게 다시 전달된다.
4. 초기 Sender은 선출된 Coordinator을 모두에게 알리고, 현재 구성원을 나타내는 두 번째 메세지를 보낸다.

 

 

Bully vs Ring

 

Bully Algorithm

• 최악의 경우 : 최초 개시자가 가장 낮은 ID를 가지는 노드 → O(N^2)
• 최선의 경우 : 개시자가 두 번째로 높은 ID를 가지는 노드 → N-2

Ring Algorithm

• 항상 2(n-1)개의 메시지
• 한 라운드는 Election Message, 한 라운드는 Coordinator Message

 

 

 

 

---

Content / Image Reference 

 

Tannenbaum and Van Steen :: Distributed Systems: Principles and Paradigms (PDF)