합의 및 조정

합의와 조정은 지연 및 오류에도 불구하고 메시지를 통해서만 통신하는 독립적인 프로세스들이 어떻게 공통된 값이나 행동에 동의할 수 있는지를 다룹니다.

Definition

합의는 각 프로세스가 값을 제안하고, 일부 프로세스가 실패하더라도 모든 프로세스가 유효한 단일 공통 값에 동의하며, 모든 올바른 프로세스가 동의하고, 모든 올바른 프로세스가 결국 결정에 도달하는 문제입니다.

Scope

이 분야는 합의 문제와 그 변형(동의, 원자적 브로드캐스트, 유효성, 종료), 결정론적 비동기 합의에 대한 기초적인 FLP 불가능성 결과, Paxos 및 Raft와 같은 실용적인 합의 프로토콜, 비잔틴 결함 허용 동의, 그리고 상호 배제 및 리더 선출과 같은 고전적인 조정 문제를 다룹니다. 이는 결함 허용 분산 컴퓨팅의 이론적이고 실용적인 핵심입니다.

Sub-topics

• Byzantine Fault Tolerance
• Distributed Consensus
• Distributed Mutual Exclusion and Leader Election
• Paxos and Raft

Core questions

• 어떤 타이밍 및 실패 모델에서 합의가 해결 가능하며, 언제 증명할 수 없을 정도로 불가능한가?
• 실용적인 프로토콜은 안전성을 유지하면서 FLP 불가능성을 어떻게 회피하는가?
• 충돌 실패와 비잔틴 실패를 허용하기 위해 얼마나 많은 복제가 필요한가?
• 프로세스는 공유 자원에 대한 접근을 조정하거나 리더를 안정적으로 선출하는 방법을 어떻게 할 수 있는가?

Key theories

FLP 불가능성

완전히 비동기적인 시스템에서는 단일 프로세스라도 충돌할 수 있는 경우, 느린 프로세스를 실패한 프로세스와 구별할 수 없으므로 결정론적 프로토콜은 합의를 보장할 수 없습니다. 이 결과는 부분 동기화, 무작위화 및 실패 감지기의 필요성을 제기합니다.

쿼럼 기반 합의

Paxos와 같은 프로토콜은 겹치는 다수(쿼럼)가 제안을 수락하도록 요구함으로써 동의를 달성합니다. 이는 두 결정이 올바른 프로세스에서 교차하도록 보장하여 라운드 및 리더 변경 전반에 걸쳐 일관성을 유지합니다.

비잔틴 동의 경계

최대 f개의 프로세스가 임의로 동작할 수 있는 상황에서 동의에 도달하려면 고전적인 동기 설정에서 최소 3f+1개의 프로세스가 필요하며, 이는 모든 비잔틴 결함 허용 시스템 설계의 기준이 되는 엄격한 경계입니다.

Clinical relevance

합의는 신뢰할 수 있는 인프라의 중추입니다. 조정 서비스, 복제된 데이터베이스, 분산 잠금, 블록체인 등 모든 시스템은 복제본의 일관성을 유지하기 위해 합의 프로토콜을 실행하며, 이는 현대 클라우드 시스템의 내구성 및 가용성 보장에 직접적인 영향을 미칩니다.

History

1982년 비잔틴 장군 문제 논문과 1985년 FLP 불가능성 결과는 동의의 한계를 규정했습니다. 램포트의 Paxos(1989년 배포, 1998년 출판)는 실용적인 비동기 안전 프로토콜을 제시했으며, 이후 비잔틴 결함 허용 및 Raft에 대한 연구는 합의를 악의적인 결함에 대해 견고하게 만들고 구현자들이 접근하기 쉽게 만들었습니다.

Debates

FLP 불가능성이 실제로 합의를 달성할 수 없게 만드는가?

FLP는 완전히 비동기적인 모델에서 항상 안전하고 활성적인 결정론적 프로토콜을 배제하지만, 실제 시스템은 점진적 동기화(eventual synchrony)를 가정하거나 무작위화를 사용하여 이를 회피합니다. 이는 안전성을 무조건적으로 유지하고 네트워크가 정상적으로 작동할 때마다 활성성을 달성합니다.

Key figures

• Leslie Lamport
• Nancy Lynch
• Michael Fischer
• Michael Paterson
• Barbara Liskov

Seminal works

• fischer1985
• lamport1998
• lamport1982byz

Frequently asked questions

합의가 분산 시스템에서 가장 어려운 문제로 간주되는 이유는 무엇인가?

원자적 브로드캐스트, 복제된 상태 머신, 분산 잠금과 같은 다른 많은 조정 작업이 합의로 귀결되며, 합의 자체는 비동기 충돌-실패 모델에서 결정론적으로 해결하는 것이 불가능하다고 증명되었기 때문입니다. 따라서 모든 해결책은 신중한 타이밍 또는 무작위성 가정을 해야 합니다.

합의는 복제된 데이터베이스와 어떤 관련이 있는가?

복제된 데이터베이스는 작업 순서에 동의함으로써 복제본의 일관성을 유지하는데, 이는 정확히 일련의 합의 결정입니다. 이것이 분산 키-값 저장소와 같은 시스템이 핵심에 합의 프로토콜을 내장하는 이유입니다.