리더 선출

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요

리더 선출은 분산 시스템에서 정확히 하나의 프로세서만 리더로 지정하는 문제이다. 이 문제는 종료, 고유성, 합의의 세 가지 조건을 충족해야 한다. 리더 선출 알고리즘은 통신 메커니즘, 프로세스 식별자, 네트워크 토폴로지, 네트워크 크기 등 여러 측면에서 다양하게 분류될 수 있다. 링 네트워크, 메쉬 네트워크, 하이퍼큐브, 완전 네트워크 등 다양한 네트워크 토폴로지에서 리더 선출 알고리즘이 연구되었으며, Shout, Mega-Merger, Yo-yo와 같은 범용 알고리즘도 개발되었다. 리더 선출은 무선 통신망 프로토콜에서 메시지 수집 및 방송과 같은 기본적인 통신 기능을 구현하는 데 활용되며, 무선 네트워크 환경에 따라 다양한 런타임이 존재한다.

더 읽어볼만한 페이지

계산 문제 - 다체 문제
다체 문제는 상호작용하는 여러 물체의 운동을 다루는 문제로, 특히 중력적으로 상호작용하는 천체들의 운동을 예측하는 문제가 대표적이며, 삼체 문제부터는 해석적 해를 구하기 어려워 섭동 이론이나 수치 해석 등의 방법이 활용된다.
계산 문제 - 최적화 문제
최적화 문제는 주어진 제약 조건 하에 특정 목적 함수의 값을 최소화하거나 최대화하는 해를 찾는 문제로, 제약 조건 유무, 함수 종류, 변수 성격에 따라 다양한 유형으로 나뉜다.
분산 컴퓨팅 문제 - 교착 상태
교착 상태는 둘 이상의 프로세스가 자원을 점유하고 서로의 자원을 요청하여 더 이상 진행할 수 없는 상태를 의미하며, 상호 배제, 점유 대기, 비선점, 순환 대기 네 가지 조건이 모두 충족되어야 발생하고, 운영 체제는 이를 예방, 회피, 무시, 발견하는 방법으로 관리한다.
분산 컴퓨팅 문제 - 비잔티움 장애 허용
비잔틴 장애 허용(BFT)은 분산 컴퓨팅 시스템에서 일부 구성 요소가 오류나 악의적인 행위를 하더라도 시스템 전체가 정상적으로 작동하도록 보장하는 속성으로, 비잔틴 장애에 대한 대응책으로 합의 알고리즘을 통해 신뢰성을 확보하며, 블록체인, 항공, 군사, 암호화폐 등 다양한 분야에서 활용된다.
분산 컴퓨팅 - 클라우드 컴퓨팅
클라우드 컴퓨팅은 인터넷을 통해 컴퓨팅 자원을 서비스 형태로 제공하는 모델로, 다양한 서비스 및 배치 모델을 가지며 비용 효율성과 확장성을 제공하지만 보안 및 의존성 문제도 존재하며 지속적으로 발전하고 있다.
분산 컴퓨팅 - 그리드 컴퓨팅
그리드 컴퓨팅은 지리적으로 분산된 컴퓨터 자원을 연결하여 가상 슈퍼컴퓨터를 구축하는 기술이며, 유휴 자원을 활용하고 과학 연구 등 다양한 분야에 활용된다.

리더 선출
개요
유형	합의 알고리즘
목적	분산 시스템에서 리더 노드 결정
특징	자동화된 프로세스 네트워크 토폴로지 및 통신 모델에 따라 다양한 알고리즘 존재
상세 내용
필요성	분산 시스템 관리를 위한 중앙 집중식 의사 결정 필요 단일 실패 지점 방지 및 시스템 복원력 향상
사용 사례	클러스터 관리 데이터베이스 복제 분산 잠금
고려 사항	알고리즘 복잡성 합의 도달 시간 통신 오버헤드 결함 허용
주요 알고리즘
고전적 알고리즘	불리 알고리즘 링 기반 알고리즘
현대적 알고리즘	Paxos Raft ZooKeeper
절충안
복잡성	알고리즘 선택은 시스템 요구 사항 및 우선 순위에 따라 달라짐
성능	성능과 결함 허용 간의 균형이 중요

2. 정의

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

# 프로세서의 상태는 선출된 상태와 선출되지 않은 상태로 나뉜다. 일단 선출되면, 선출된 상태로 유지되고, 선출되지 않은 경우에도 마찬가지이다.

# 모든 실행에서 정확히 하나의 프로세서가 선출되고, 나머지는 자신이 선출되지 않았음을 결정한다.

2. 1. 리더 선출 알고리즘의 조건

유효한 리더 선출 알고리즘은 다음 조건을 충족해야 한다.^[28]^[4]

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

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

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

2. 2. 리더 선출 알고리즘의 다양성

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

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

3. 알고리즘

알고리즘은 분산 컴퓨팅 환경에서 리더를 선출하는 데 사용되는 절차이다. 리더 선출은 네트워크 토폴로지에 따라 다양한 방식으로 수행될 수 있다.
링 네트워크

링 네트워크는 각 노드가 정확히 두 개의 다른 노드에 연결된 형태이다. 링은 단방향 또는 양방향일 수 있다.

익명 링: 모든 프로세서가 동일한 상태를 가지는 링이다. 익명 링에서는 프로세서의 상태가 동일하고 동일한 절차를 실행하기 때문에 대칭성을 깰 수 없어 결정론적 리더 선출 알고리즘이 존재하지 않는다.^[3]^[6]
확률적 리더 선출: 익명 링에서 리더를 선출하기 위해 확률적 알고리즘을 사용할 수 있다. 프로세서는 확률적 함수를 기반으로 식별자를 정하고 이를 네트워크에 전달하여 리더를 선택한다.
고유 ID를 가진 링: 각 프로세서가 고유 ID를 가지는 경우, 창과 로버츠 알고리즘^[14]은 가장 높은 ID를 가진 프로세서를 리더로 선택한다. 히르시버그와 싱클레어 알고리즘^[15]은 양방향 메시지 전달 방식을 통해 이를 개선했다.

메쉬 네트워크

메쉬는 병렬 시스템 등에서 사용되는 네트워크 토폴로지이다.^[16] 노드는 모서리, 경계, 내부로 구성된다.

무방향 메쉬: 일반적인 무방향 메쉬에서 리더 선출 알고리즘은 네 모서리 노드 중 하나를 리더로 선출한다.^[17]
방향성 메쉬: 방향성 메시는 포트 번호가 방위 레이블(북, 남, 동, 서)을 가지는 특수한 경우이다. 리더 선출은 특정 모서리(예: "북"과 "동")를 지정하여 해당 노드가 리더임을 알리는 방식으로 간단하게 해결할 수 있다.

토러스

토러스는 "랩 어라운드(wrap-around)" 기능을 가진 메시 아키텍처의 특별한 경우이다. 각 노드는 정확히 4개의 연결된 에지를 갖는다. 리더 선출은 선출 단계를 사용하여 잠재적 후보를 제거하고 최종적으로 하나의 리더를 남기는 방식으로 수행될 수 있다.^[16]
하이퍼큐브

하이퍼큐브는 각 노드가 특정 차수를 가지는 네트워크이다. 선출 단계를 사용하여 리더를 선출할 수 있으며, 각 단계에서 결투자 간의 경쟁을 통해 리더를 결정한다.
완전 네트워크

완전 네트워크는 모든 프로세서가 서로 연결된 구조이다. O(n) 메시지 및 공간 복잡도를 가진 최적의 솔루션이 알려져 있다.^[20] 이 알고리즘에서 프로세서는 더미, 수동, 후보 상태를 가지며, 우선 순위 체계를 기반으로 리더를 선출한다.

3. 1. 링 네트워크에서의 리더 선출

링 네트워크는 각 노드가 정확히 두 개의 다른 노드에 연결된 연결 그래프 토폴로지이다. n개의 노드를 가진 그래프의 경우 노드를 연결하는 n개의 에지가 있다. 링은 단방향일 수 있는데, 이 경우 프로세서는 한 방향으로만 통신한다(노드는 왼쪽으로만 메시지를 보내거나 오른쪽으로만 메시지를 보낼 수 있다). 또는 양방향일 수 있는데, 이 경우 프로세서는 양방향으로 메시지를 송수신할 수 있다(노드는 왼쪽과 오른쪽으로 메시지를 보낼 수 있다).

3. 1. 1. 익명 링

익명 링은 모든 프로세서가 동일한 경우를 말한다. 좀 더 형식적으로는, 시스템은 모든 프로세서에 대해 동일한 상태 기계를 갖는다.^[3] 네트워크의 크기가 프로세스에 알려져 있더라도 익명 링에서 리더를 선출하는 결정론적 알고리즘은 없다.^[3]^[6] 이는 모든 프로세스가 동일한 속도로 실행될 경우 익명 링에서 대칭성을 깰 가능성이 없기 때문이다. 일정 단계 후 프로세서의 상태는 인접 노드의 초기 상태에만 의존한다. 따라서 상태가 동일하고 동일한 절차를 실행하기 때문에, 매 라운드마다 각 프로세서가 동일한 메시지를 보낸다. 따라서 각 프로세서의 상태도 동일하게 변경되며, 결과적으로 한 프로세서가 리더로 선출되면 다른 모든 프로세서도 마찬가지이다.

간단하게, 익명 동기 링에서 이에 대한 증명을 제시한다. 귀류법에 의한 증명이다. 크기가 n>1인 익명 링 R을 고려한다. 이 익명 링 R에서 리더 선출 문제를 해결하는 알고리즘 "A"가 존재한다고 가정한다.^[3]

:'''''보조 정리''': R에서 A의 허용 가능한 실행의

k

라운드 후, 모든 프로세스는 동일한 상태를 갖는다.

'''증명.'''

k

에 대한 수학적 귀납법으로 증명한다.

'''기저 사례:'''

k=0

: 모든 프로세스는 초기 상태에 있으므로 모든 프로세스가 동일하다.

'''귀납적 가설:'''

k-1

라운드에 대해 보조 정리가 참이라고 가정한다.

'''귀납적 단계:''' 라운드

k

에서 모든 프로세스는 동일한 메시지

m_r

을 오른쪽으로 보내고 동일한 메시지

m_l

을 왼쪽으로 보낸다. 모든 프로세스가 라운드

k-1

후 동일한 상태에 있으므로, 라운드 k에서 모든 프로세스는 왼쪽 가장자리로부터 메시지

m_r

을 수신하고 오른쪽 가장자리로부터 메시지

m_l

을 수신한다. 모든 프로세스가 라운드

k

에서 동일한 메시지를 수신하므로, 라운드

k

후 동일한 상태에 있다.

위의 보조 정리는 A의 실행에서 유한한 수의 라운드 후, 한 프로세스가 선출된 상태에 들어가고 다른 프로세스가 비선출 상태에 들어간다는 사실과 모순된다.

3. 1. 2. 확률적 리더 선출

익명 링에서 리더 선출 문제를 해결하는 일반적인 방법은 확률적 알고리즘을 사용하는 것이다. 이러한 접근 방식에서, 프로세서는 보통 확률적 함수를 기반으로 특정 식별자를 정하고 이를 네트워크의 다른 부분에 전달한다. 결국 알고리즘을 적용하여 (높은 확률로) 리더를 선택한다.

3. 1. 3. 고유 ID를 가진 링

각 프로세서가 고유 ID를 가지는 경우, 창과 로버츠^[14]는 가장 높은 ID를 가진 프로세서가 리더로 선택되는 균일한 알고리즘을 제안했다. 각 프로세서는 시계 방향으로 자신의 ID를 보낸다. 프로세서는 메시지를 수신하고 ID를 자신의 ID와 비교한다. ID가 더 크면 프로세서는 메시지를 전달하고, 그렇지 않으면 메시지를 폐기한다. 이 알고리즘은 최악의 경우

O(n^2)

개의 메시지를 사용하고 평균적인 경우

O(n \log n)

개의 메시지를 사용한다.

히르시버그와 싱클레어^[15]는 양방향 메시지 전달 방식을 도입하여 이 알고리즘을

O(n \log n)

의 메시지 복잡도로 개선했다.

3. 2. 메쉬 네트워크에서의 리더 선출

메쉬는 병렬 시스템, 중복 메모리 시스템 및 상호 연결 네트워크에서 많이 사용되는 네트워크 토폴로지이다.^[16] 메쉬 구조에서 노드는 모서리(이웃이 두 개뿐), 경계(이웃이 세 개뿐) 또는 내부(이웃이 네 개)로 구성된다. 크기가 a x b인 메쉬의 엣지 수는 m=2ab-a-b이다.

3. 2. 1. 무방향 메쉬

일반적인 무방향 메쉬에서 리더 선출 알고리즘은 네 모서리 노드 중 하나만 리더로 선출한다.^[17] 모서리 노드는 다른 프로세스의 상태를 알지 못할 수 있으므로, 알고리즘은 먼저 모서리 노드를 깨워야 한다. 리더는 다음과 같이 선출될 수 있다.

# '''웨이크업 프로세스''': 이 과정에서 k개의 노드가 선출 과정을 시작한다. 각 시작자는 웨이크업 메시지를 모든 인접 노드로 보낸다. 노드가 시작자가 아니면 단순히 메시지를 다른 노드로 전달한다. 이 단계에서 최대 3n+k개의 메시지가 전송된다.

# '''선출 프로세스''': 외부 링의 선출은 최대 두 단계로 이루어지며 6(a+b)-16개의 메시지가 사용된다.

# '''종료''': 리더는 모든 노드에 종료 메시지를 보낸다. 이 과정은 최대 2n개의 메시지를 필요로 한다.

메시지 복잡도는 최대 6(a + b) - 16이며, 메시가 정사각형 모양인 경우 O(√n)이다.

3. 2. 2. 방향성 메쉬

방향성 메시는 포트 번호가 방위 레이블(북, 남, 동, 서)을 가지는 특수한 경우이다. 방향성 메시에서의 리더 선출은 "북"과 "동"과 같은 모서리를 지정하고 해당 노드가 리더임을 알도록 하는 방식으로 간단하게 해결할 수 있다.

3. 2. 3. 토러스

토러스는 "랩 어라운드(wrap-around)" 기능을 가진 메시 아키텍처의 특별한 경우이다. 이 구조에서 각 노드는 정확히 4개의 연결된 에지를 갖는다.

이러한 구조에서 리더를 선출하는 한 가지 방법은 선출 단계를 사용하는 것이다. 링 구조의 절차와 유사하게, 이 방법은 각 단계에서 잠재적 후보를 제거하여 결국 하나의 후보 노드만 남게 한다. 이 노드가 리더가 되어 모든 다른 프로세스에 종료를 알린다.^[16] 이 접근 방식은 O(n)의 복잡성을 달성하는 데 사용될 수 있다. 네트워크에서 결함이 있는 링크가 존재하는 경우를 처리하기 위해 더 실용적인 접근 방식도 도입되었다.^[18]^[19]

3. 3. 하이퍼큐브에서의 리더 선출

하이퍼큐브

H_k

는

n=2^k

개의 노드로 구성된 네트워크이며, 각 노드는 차수

k

와

O(n \log n)

개의 에지를 갖는다.

이전과 유사한 선출 단계를 사용하여 리더 선출 문제를 해결할 수 있다. 각 단계에서 두 개의 노드(결투자라고 함)가 경쟁하며 승자는 다음 단계로 진출한다. 이는 각 단계에서 결투자의 절반만 다음 단계로 진입한다는 것을 의미한다. 이 절차는 단 한 명의 결투자만 남을 때까지 계속되며, 이 결투자가 리더가 된다. 일단 선택되면, 다른 모든 프로세스에 알린다. 이 알고리즘은

O(n)

개의 메시지를 필요로 한다. 비방향성 하이퍼큐브의 경우, 이와 유사한 접근 방식을 사용할 수 있지만, 메시지 복잡성은

O(n \log \log n)

으로 더 높다.^[16]

3. 4. 완전 네트워크에서의 리더 선출

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

# 더미: 리더 선출 알고리즘에 참여하지 않는 노드.

# 수동: 시작 전 프로세스의 초기 상태.

# 후보: 깨어난 후 노드의 상태. 후보 노드는 리더가 될 것으로 간주된다.

노드는 시스템의 전체 노드 집합을 알지 못하지만, 이 배열에서 모든 노드가 자신의 단일 후계자의 식별자(이웃이라고 함)를 알고 있으며,^[20] 모든 노드는 다른 노드에 의해 알려져야 한다는 가정이 있다.^[21]

모든 프로세서는 처음에 수동 상태로 시작하여 깨어날 때까지 대기한다. 노드가 깨어나면 리더가 되기 위한 후보가 된다. 우선 순위 체계를 기반으로, 후보 노드는 가상 링에서 협력한다. 어느 시점에서 후보는 링에서 자신보다 앞에 있는 후보의 신원을 알게 된다. 우선 순위가 높은 후보는 우선 순위가 낮은 후보에게 선행자에 대해 묻는다. 우선 순위가 낮은 후보는 우선 순위가 높은 후보에게 응답한 후 더미가 된다. 이 체계를 기반으로, 가장 높은 우선 순위의 후보는 결국 시스템의 모든 노드가 자신을 제외하고 더미라는 것을 알게 되며, 이 시점에서 자신이 리더임을 알게 된다.

위의 알고리즘은 정확하지 않으며, 추가 개선이 필요하다.^[21]

4. 범용 리더 선출 기법

범용 리더 선출 기법은 네트워크 토폴로지나 속성에 대한 사전 지식 없이 모든 프로세스 네트워크에서 사용할 수 있도록 설계되었다.^[16]

4. 0. 1. Shout

Shout 프로토콜은 일반적인 그래프에서 스패닝 트리를 구축하고 그 루트를 리더로 선출한다. 이 알고리즘은 에지(edge)의 수에 비례하는 총 비용을 갖는다.

4. 0. 2. [[Mega-Merger]]

이 기법은 트리의 루트가 리더가 되는 최소 신장 트리(MST)를 찾는 것과 유사하다. 개별 노드가 서로 "병합"되어 더 큰 구조를 형성한다. 이 알고리즘의 결과는 전체 시스템의 리더가 루트인 트리(사이클이 없는 그래프)이다. 메가-머저 방법의 비용은 O|오^영어(m+n log n)이며, 여기서 m은 간선의 수이고 n은 노드의 수이다.

4. 0. 3. Yo-yo

요요 알고리즘은 전처리 단계와 일련의 반복으로 구성된 최소값 찾기 알고리즘이다.^[16] 첫 번째 단계(''설정'' 단계)에서 각 노드는 자신의 ID를 모든 이웃과 교환하고, 그 값을 기반으로 인접한 에지의 방향을 설정한다. 예를 들어 노드 x의 ID가 y보다 작으면 x는 y를 향한다. 모든 이웃보다 작은 ID를 가지는 노드는 '''소스'''가 된다. 반대로 모든 들어오는 에지(즉, 모든 이웃보다 큰 ID)를 가진 노드는 '''싱크'''가 된다. 그 외의 모든 노드는 '''내부''' 노드이다.

모든 에지의 방향이 설정되면 ''반복'' 단계가 시작된다. 각 반복은 일부 후보가 제거되는 선거 단계이다. 각 반복은 ''YO-''와 ''–YO''의 두 단계로 진행된다. 이 단계에서 소스는 연결된 싱크로 소스의 최소값을 전파하는 프로세스를 시작한다.

'''Yo-'''

1. 소스(지역 최소값)는 자신의 값을 모든 나가는 이웃에게 전송한다.

2. 내부 노드는 모든 들어오는 이웃으로부터 값을 수신할 때까지 기다린다. 최소값을 계산하여 나가는 이웃에게 보낸다.

3. 싱크(나가는 에지가 없는 노드)는 모든 값을 수신하고 최소값을 계산한다.

'''-yo'''

1. 싱크는 최소값을 보낸 이웃에게 YES를 보내고, 다른 이웃에게는 NO를 보낸다.

2. 내부 노드는 최소값을 수신한 모든 들어오는 이웃에게 YES를 보내고, 다른 이웃에게는 NO를 보낸다. 하나의 NO만 수신하면 모두에게 NO를 보낸다.

3. 소스는 모든 투표를 받을 때까지 기다린다. 모두 YES인 경우 생존하고, 그렇지 않으면 더 이상 후보가 아니다.

4. 노드 x가 들어오는 이웃 y에게 NO를 보내면 해당 에지의 논리적 방향이 반전된다.

5. 노드 y가 나가는 이웃으로부터 NO를 수신하면 해당 링크의 방향을 전환한다.

최종 단계 이후, NO를 수신한 소스는 더 이상 소스가 아니며 싱크가 된다.

유용한 노드를 제거하기 위해 추가 단계인 ''가지치기''가 도입된다. 즉, 다음 반복에 영향을 미치지 않는 노드를 제거한다.

1. 싱크가 리프 노드인 경우, 유용하지 않으므로 제거한다.

2. YO- 단계에서 노드가 둘 이상의 들어오는 이웃으로부터 동일한 값을 수신하는 경우, 하나를 제외한 모든 노드에게 연결된 링크를 제거하도록 요청한다.

이 방법의 총 비용은 O(m log n) 메시지이다. 가지치기를 포함한 실제 메시지 복잡성은 열린 연구 문제이며 알려져 있지 않다.

5. 응용

리더 선출은 다양한 분산 시스템 및 네트워크 환경에서 활용된다.

5. 1. 무선 네트워크

무선 통신망 프로토콜에서 리더 선출은 메시지 수집이나 방송과 같은 고급 통신을 위한 첫 단계로 자주 활용된다.^[22] 무선 네트워크는 인접 노드가 동시에 전송할 때 충돌이 발생하기 때문에, 리더를 선출하여 이 과정을 효율적으로 조정할 수 있다. 네트워크의 지름 ''D''는 리더 선출에 필요한 시간의 하한을 나타내지만, 리더 선출 문제의 상한과 하한은 연구되는 특정 무선 모델에 따라 달라진다.

5. 1. 1. 모델 및 런타임

무선 네트워크에서 ''n''개의 노드는 매 라운드마다 메시지를 전송하거나 수신할 수 있다. ''충돌 감지'' 가능 여부에 따라 노드는 침묵 상태, 단일 메시지 수신, 또는 다중 메시지 수신(내용 해독 불가)을 구별할 수 있다. ''삐 소리 모델''에서는 반송파 감지를 통해 침묵 또는 최소 하나의 메시지 존재 여부를 구별한다.

단일 홉 및 다중 홉 네트워크에서 리더 선출에 필요한 런타임은 네트워크 모델에 따라 달라지며, 그 범위는 다음과 같다.

네트워크 유형	모델	런타임
단일 홉	충돌 감지 (예상)	상수
단일 홉	충돌 감지 없음 (결정론적)	O(n log n) 라운드
다중 홉	삐 소리 모델 (높은 확률)	O((D+ log n)(log² log n)) 라운드
다중 홉	삐 소리 모델 (결정론적)	O(D log n)
다중 홉	충돌 감지 (결정론적)	O(n)
다중 홉	충돌 감지 없음 (결정론적)	O(n log^3/2 n (log log n)^0.5) 라운드

참조

_[1] 논문 A Distributed Algorithm for Minimum-Weight Spanning Trees http://theory.csail.[...] 2007-09-30
_[2] 논문 A Modular Technique for the Design of Efficient Distributed Leader Finding Algorithms
_[3] 서적 Distributed Computing: Fundamentals, Simulations and Advance Topics John Wiley & Sons Inc. 2004
_[4] 간행물 A Probabilistically Correct Leader Election Protocol for Large Groups Cornell University 2000
_[5] 간행물 "Leader Election in Anonymous Rings:Franklin Goes Probabilistic" 2008
_[6] 간행물 "Computing on an anonymous ring" 1988
_[7] 간행물 "Symmetry breaking in distributed networks" 1990
_[8] 간행물 "Self-Stabilizing Token Circulation on Anonymous Message Passing Rings" 1998
_[9] 간행물 "Deterministic, constant space, self-stabilizing leader election on uniform rings." 1995
_[10] 간행물 "Uniform self-stabilizing rings" 1989
_[11] 간행물 "Probabilistic self-stabilization" 1990
_[12] 서적 Introduction to Distributed Algorithms Cambridge University Press 2000
_[13] 간행물 "Self-stabilizing leader election in networks of _nite-state anonymous agents" 2006
_[14] 간행물 "An improved algorithm for decentralized extrema-finding in circular configurations of processes" 1979
_[15] 간행물 "Decentralized extrema-finding in circular configurations of processors" 1980
_[16] 서적 Design and Analysis of Distributed Algorithms Wiley 2006
_[17] 간행물 "Election in Mesh, Cube and Complete Networks" 2007
_[18] 간행물 "Leader Election Algorithm in 2D Torus Network with the Presence of One Link Failure" 2010
_[19] 간행물 "Dynamic Leader Election Algorithm in 2D Torus Network with Multi Links Failure" 2014
_[20] 간행물 "Efficient leader election in complete networks" 2005
_[21] 간행물 "A Modified O(n) Leader Election Algorithm for Complete Networks." IEEE 2007
_[22] 서적 Near Optimal Leader Election in Multi-Hop Radio Networks 2013
_[23] 논문 A Distributed Algorithm for Minimum-Weight Spanning Trees http://theory.csail.[...]
_[24] 논문 A Modular Technique for the Design of Efficient Distributed Leader Finding Algorithms
_[25] 저널 A Distributed Algorithm for Minimum-Weight Spanning Trees http://theory.csail.[...] 2018-12-03
_[26] 저널 A Modular Technique for the Design of Efficient Distributed Leader Finding Algorithms https://archive.org/[...] 1990
_[27] 서적 Distributed Computing: Fundamentals, Simulations and Advance Topics John Wiley & Sons inc. 2004
_[28] 간행물 A Probabilistically Correct Leader Election Protocol for Large Groups Cornell University 2000
_[29] 간행물 "Leader Election in Anonymous Rings:Franklin Goes Probabilistic" 2008

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com