분산 상호 배제 및 리더 선출

상호 배제와 리더 선출은 고전적인 조정 문제입니다. 즉, 하나의 프로세스만이 중요한 자원에 접근하도록 보장하고, 동료들 중에서 단일의 구별되는 조정자를 선택하는 것입니다.

Definition

분산 상호 배제는 모든 요청자에게 궁극적인 접근을 보장하면서 한 번에 하나의 프로세스만 공유 자원을 보유하도록 보장합니다. 리더 선출은 모든 프로세스가 결과에 동의하는 단 하나의 프로세스를 조정자로 결정론적으로 선택합니다.

Scope

이 주제는 허가 기반 상호 배제 알고리즘(Lamport의 타임스탬프 알고리즘, Ricart-Agrawala, Maekawa의 쿼럼 접근 방식)과 토큰 기반 알고리즘, 그리고 이들의 메시지 복잡성 및 공정성 속성을 다룹니다. 또한 링(Chang-Roberts) 및 일반 네트워크(불리 알고리즘)를 위한 리더 선출 알고리즘과 식별자 및 동기화에 대한 가정을 포함합니다. 이러한 기본 요소들은 조정 서비스 및 복제 시스템 전반에 걸쳐 반복적으로 나타납니다.

Core questions

• 프로세스는 메시지만을 사용하여 공유 자원에 대한 접근을 직렬화할 수 있는가?
• 허가 기반 및 토큰 기반 방식 간의 메시지 복잡성 및 공정성 절충점은 무엇인가?
• 고유한 리더는 어떻게 선택되며, 리더 실패 후 선출은 어떻게 다시 트리거되는가?

Key theories

허가 기반 상호 배제

Ricart-Agrawala와 같은 알고리즘은 논리적 타임스탬프에 따라 요청을 정렬하고, 요청자가 모든(또는 쿼럼의) 동료로부터 허가를 받으면 진입을 허용하여, 임계 구역 진입당 제한된 메시지 비용으로 공정성을 달성합니다.

토큰 기반 상호 배제

고유한 토큰이 순환하거나 필요에 따라 요청되며, 토큰 소유자만이 임계 구역에 진입할 수 있어 메시지 트래픽을 줄이지만, 실패 후 손실된 토큰을 재생성하기 위한 메커니즘이 필요합니다.

리더 선출

링을 위한 Chang-Roberts 및 일반 네트워크를 위한 불리 알고리즘과 같은 선출 알고리즘은 프로세스 식별자를 사용하여 모든 올바른 프로세스가 인식하는 단일 최고 우선순위 조정자로 수렴합니다.

Clinical relevance

리더 선출은 복제 시스템이 주(primary) 또는 조정자를 선택해야 할 때마다 호출되며, 분산 잠금은 상호 배제를 일반화합니다. 둘 다 클라우드 인프라 전반에 사용되는 조정 시스템에 의해 핵심 서비스로 노출됩니다.

History

Lamport의 1978년 논리 시계 논문은 타임스탬프 기반 상호 배제 알고리즘을 소개했습니다. Ricart와 Agrawala는 1981년에 이를 최적화했고, Maekawa는 얼마 지나지 않아 쿼럼을 도입했으며, Garcia-Molina의 1982년 불리 알고리즘은 리더 선출을 공식화하여 이 분야에 표준적인 조정 알고리즘을 제공했습니다.

Key figures

• Leslie Lamport
• Glenn Ricart
• Ashok Agrawala
• Hector Garcia-Molina

Seminal works

• ricart1981
• garcia-molina1982
• lynch1996

Frequently asked questions

분산 상호 배제는 단일 머신의 잠금과 어떻게 다른가?

의존할 공유 메모리나 중앙 잠금 관리자가 없으므로, 프로세스는 순전히 메시지 교환을 통해 조정해야 하며, 단일 머신 잠금이 당연하게 여길 수 있는 메시지 지연 및 실패를 명시적으로 처리해야 합니다.