괴롭힘 알고리즘

분산 컴퓨팅에서, 불량 알고리즘은 분산된 컴퓨터 프로세스 그룹으로부터 코디네이터나 리더를 동적으로 선출하는 방법이다.불합격 처리된 프로세스 중 프로세스 ID 번호가 가장 높은 프로세스를 코디네이터로 선택한다.

가정

알고리즘은 다음과 같이 가정한다.^[1]

시스템은 동기식이다.
알고리즘의 실행 중을 포함하여, 프로세스는 언제든지 실패할 수 있다.
프로세스가 중지됨으로써 실패하고 재시작하여 실패로부터 되돌아온다.
실패한 프로세스를 감지하는 고장 검출기가 있다.
프로세스 간 메시지 전달은 신뢰할 수 있다.
각 프로세스는 자신의 프로세스 ID와 주소, 그리고 다른 모든 프로세스의 프로세스 ID를 알고 있다.

알고리즘.

알고리즘은 다음과 같은 메시지 유형을 사용한다.

선거 메시지:선거를 알리기 위해 보내졌다.
응답(알리브) 메시지:선거 메시지에 응답한다.
코디네이터(승리) 메시지:선거의 승자가 승리를 발표하기 위해 보낸 것이다.

프로세스가 있을 때P고장으로부터 복구되거나, 고장 검출기는 현재 코디네이터가 고장났음을 표시한다.P다음 작업을 수행하십시오.

만약P프로세스 ID가 가장 높으며, 다른 모든 프로세스에 승리 메시지를 보내고 새로운 코디네이터가 된다.그렇지 않으면P자체보다 프로세스 ID가 높은 다른 모든 프로세스에 선거 메시지를 브로드캐스트한다.
만약P선거 메시지를 보낸 후 응답을 수신하지 않으면 다른 모든 프로세스에 승리 메시지를 브로드캐스트하고 코디네이터가 된다.
만약PID가 더 높은 프로세스로부터 응답을 수신하며, 이 선택에는 더 이상의 메시지를 보내지 않고 승리 메시지를 기다린다.(시간 경과 후 승리 메시지가 없을 경우, 처음부터 프로세스를 재시작한다.)
만약P낮은 ID의 다른 프로세스로부터 선거 메시지를 수신하여 응답 메시지를 다시 전송하고, 번호가 높은 프로세스에 선거 메시지를 전송하여 처음부터 선거 프로세스를 시작한다.
만약P코디네이터 메시지를 수신하고, 발신인을 코디네이터로 취급한다.

분석

안전

지도자 선거 프로토콜의 안전 속성은 모든 비과실 프로세스가 프로세스를 선택한다는 것이다.Q또는 전혀 선출하지 않는다.리더를 선출하는 모든 프로세스는 동일한 프로세스를 결정해야 한다는 점에 유의하십시오.Q지도자로서Bully 알고리즘은 (지정된 시스템 모델에 따라) 이 속성을 만족시키며, 선거 중을 제외하고 그룹의 두 프로세스가 리더가 누구인지에 대한 상반된 견해를 갖는 것은 어느 시점에서도 불가능하다.그렇지 않다면 두 가지 과정이 있기 때문이다.X그리고Y두 사람 다 그룹에게 코디네이터(승리) 메시지를 보낼 수 있도록이 말은X그리고Y서로 승리 메시지를 보냈을 거야그러나 승리 메시지를 보내기 전에 두 사람 사이에 선거 메시지가 교환되었을 것이고, 두 사람 중 낮은 프로세스 ID를 가진 과정은 결코 승리 메시지를 보내지 않을 것이기 때문에 이것은 있을 수 없다.우리는 모순을 가지고 있으며, 따라서 시스템에는 주어진 시간에 두 명의 리더가 있다는 우리의 초기 가정은 거짓이며, 그것은 불량 알고리즘이 안전하다는 것을 보여준다.

리브

리빙은 동기식 충돌 복구 모델에서도 보장된다.응답(알리브) 메시지를 보낸 후 코디네이터(승리) 메시지를 보내기 전에 리더가 실패했다고 간주하십시오.낮은 ID 프로세스에 설정된 시간 초과 전에 복구되지 않으면, 그 중 하나가 결국 리더가 된다(다른 프로세스의 일부가 충돌하더라도).실패한 과정이 제때에 복구된다면, 그것은 단지 모든 그룹에게 코디네이터(승리) 메시지를 보낸다.

네트워크 대역폭 사용률

괴롭히는 알고리즘 메시지가 고정(알고 불변) 크기라고 가정하면, ID가 가장 낮은 프로세스가 선거를 시작할 때 그룹에서 가장 많은 수의 메시지가 교환된다.이 프로세스는 (N-1) 선거 메시지를 보내고, 다음으로 높은 ID를 보내는 (N-2) 메시지 등을 전송하며, 따라서 $\Theta \left(N^{2}\right)$ ( $\Theta \left(N^{2}\right)$ $\Theta \left(N^{2}\right)$ ) ${\$ 개의 $\Theta \left(N^{2}\right)$ 선거 메시지를 발생시킨다.There are also the $\Theta \left(N^{2}\right)$ Alive messages, and $\Theta \left(N\right)$ co-ordinator messages, thus making the overall number messages exchanged in the worst case be $\Theta \left(N^{2}\right)$ .

참고 항목

참조

^ Coulouris, George; Dollimore, Jean; Kindberg, Tim (2000). Distributed Systems: Concepts and Design (3rd ed.). Addison Wesley. ISBN 978-0201619188.

위첼, 에멧(2005)"분산 조정"2005년 5월 4일 회수.
Hector Garcia-Molina, 분산 컴퓨팅 시스템, IEEE 컴퓨터 거래, Vol. C-31, 1월(1982년) 48–59
L. 램포트, R.쇼스탁, 그리고 M.Pease, "비잔틴 장군 문제" ACM Transactions on Programming Language and Systems, 제4권, 제3권, 1982년 7월.

외부 링크

위키미디어 커먼스의 Bully 알고리즘과 관련된 미디어

[1] Coulouris, George; Dollimore, Jean; Kindberg, Tim (2000). Distributed Systems: Concepts and Design (3rd ed.). Addison Wesley. ISBN 978-0201619188.

[1]

Search

괴롭힘 알고리즘

네임스페이스

더

목차

가정

알고리즘.

분석

안전

리브

네트워크 대역폭 사용률

참고 항목

참조

외부 링크