분산 시스템의 투표 알고리즘

Question

은 분산 시스템 네트워크를 가정합니다. 각 시스템은 값을 측정합니다. 모든 가치에 따라 모든 시스템이 합의하여 올바른 결정이 내려집니다. 통신 링크가 끊어 질 수 있습니다. 이 경우 투표 및 동기화 알고리즘이 있습니까? 분산 시스템에서 투표 알고리즘의

Answer 1

예 :

1. 깡패 알고리즘 (http://en.wikipedia.org/wiki/Bully_algorithm)
2. 장과 로버트 알고리즘 (http://en.wikipedia.org/wiki/Chang_and_Roberts_algorithm)

Answer 2

나는 비슷한 문제를 해결했다. 이것은 장애 탐지 체계이므로 OP의 일반적인 용어 대신이 용어로 설명 할 것입니다.

클라이언트가 주기적으로 서버에 ping을 보내고 얼마 동안 ping이 발생하지 않으면 클라이언트는 네트워크 파티션의 뒤쪽이나 죽은 것으로 간주됩니다. 클라이언트는 연결하기 위해 임의의 서버를 선택할 수 있기 때문에 다른 서버는 클라이언트가 죽었는지 아니면 살아 있는지에 대해 서로 다른 시각을 가지고 있습니다.

저희 서버는 gossip/epidemic protocol을 사용하여 고객의 의견을 서로 교환합니다. 이것은 논리가 하나의 서버의 데이터가 다른 서버의 데이터보다 우수하다는 점입니다.. 유행 프로토콜에 대한 좋은 점은 네트워크에서 가볍지 만 여전히 수렴한다는 것입니다.

결정이 내려지면 (우리의 경우 클라이언트가 죽었다 고 선언 한 경우) 모든 서버가 모든 클라이언트 하트 비트에 대해 허용 가능한 최신 테이블을 갖습니다. 모든 서버는 결정을 내릴 자유가 있으며, 우리는 합의 프로토콜 (Paxos 또는 Raft)을 통해이를 수행합니다. 서버 은 일 수 있습니다. 그 결정은 —입니다. 그러나 다소 최신의 테이블은 없지만 여전히 성공적인 Paxos 라운드를 실행하는 것은 아닙니다.