Distributed Mutual Exclusion : 동 료 형성

Question

저는 Quorums의 개념에 기반한 분산 상호 배제 알고리즘을 연구했습니다.

인용 : 동인 C는 집합 집합으로 정의되며, 집합 g ∈ C는 집합으로 불립니다.

다음 등록 동인 정원 회에 대해 길게

1) 교차 속성 : 모든 정수 g의 경우, H ∈ C, H = g ∩ ∅. 예를 들어, 첫 번째 세트와 세 번째 세트에는 공통 요소가 없으므로 세트 {1,2,3}, {2,5,7} 및 {5,7,9}을 (를) 동 단위로 쿼럼으로 지정할 수 없습니다.

2) 최소 성질 : 동등한 사람 C 안에 어떤 정족수 g, h도 없을 것. 그 g ⊇ h. 예를 들어, 집합 {1,2,3}과 {1,3}은 두 번째 집합의 수퍼 세트이므로 동인에서 쿼럼이 될 수 없습니다.

분산 시스템에서 노드 집합이 주어지면 이러한 노드들로 구성된 코토리 또는 쿼럼 집합은 어떤 방식입니까? 이 작업을 수행 할 알고리즘 또는 기술은 무엇입니까?

UPDATE : 은 다른 말로 문제를 넣으려면 - "을 감안할 때 'N'노드, 그들 중 두 사람은 공통점이 노드의 'J'수를 갖도록 'K'정원 회를 구성하는 가장 좋은 방법은 무엇입니까? "

Answer 1

읽기 또는 쓰기를위한 간단한 알고리즘은 쿼럼의 모든 노드를 읽고 쿼럼의 모든 노드에 기록해야한다는 것입니다. 이렇게하면 시스템의 다른 모든 당사자가 최신 기록 항목을 읽을 수 있습니다.

제목이 상호 배제에 관한 것이므로 시스템의 피어는 쿼럼의 모든 노드에 리소스에 대한 잠금을 요청할 수 있습니다. 첫 번째 규칙으로 인해 다른 피어가 전체 쿼럼에서 잠금을 해제 할 수 없습니다.

실제로 저는 여러분이 실제로 임의의 노드에 접속하여 정족수 n/2 + 1으로 사용한다는 것을 알고 있습니다 만,보다 정교한 배포판을 정의하여 더 작은 정족수를 지정할 수 있으므로 성능이 향상됩니다.

업데이트 :

• 2 정원 회 : 9 개 서버와 같은 정원 회에 대한

  예는 다음이 될 수 서버 1-5 인 하나 정족수와 5-9 다른 (과반수 것)

• 3 개의 쿼럼 : 서버 1,2,3,4; 4,5,6,7; 그리고 7,8,9,1은 3 가지 다른 정족수가 될 수있다.
• 더 많은 정족수 : 서버 1,2,3; 3,4,5; 5,6,1; 6,7,3; 8,3,1; 9,3,1; 6 개의 다른 정족수가 될 수 있습니다. 그러나 여기서는 서버 1과 서버 3이 각각 4 개의 쿼럼의 일부인 것을 볼 수 있으며 이러한 이유 때문에 더 많은 트래픽을 처리해야합니다.
• 1,2와 같은 쿼럼을 만들 수도 있습니다. 1,3; 1,4; 1,5; 1,6; 1,7; 1,8; 1,9; 하지만 이것은 서버 1을 가지고있는 것과 같습니다.