합의 (컴퓨터 과학)

분산 컴퓨팅과 다중 에이전트 시스템에서 프로세스들이 사용할 값을 하나로 결정하는 문제를 합의 문제 (Consensus Problem)라고 한다. 합의 적용의 사례는 데이터 베이스로의 트랜젝션 전송, 리더 식별자 일치화, 상태 기계 접근법, 아토믹 브로드캐스트가 있다. 실생활에서의 사례로는 시간 동기화, 의사 결정, 페이지랭크, 스마트 그리드, 상태 추정, 무인 항공기의 제어, 부하분산 등이 있다.

합의 문제 (Consensus Problem)는 어떤 자료 값에 대해 여러 프로세스들 (또는 에이전트들) 간의 일치성을 요구한다. 하지만 몇몇 프로세스들은 고장나거나 다른 이유로 인해 믿을 수 없게 될 수 있으며, 따라서 합의 프로토콜은 장애 허용이거나 복원력이 있어야 한다. 장애를 허용하는 합의 프로토콜은 다음과 같은 속성을 지닌다.^[1]

1. 유한성 (Termination) : 결과적으로 모든 정상적인 프로세스들은 어떤 값을 정한다.

2. 무결성 (Integrity) : 만약 모든 정상적인 프로세스들이 같은 값 v를 제안했었다면, 정상적인 프로세스들은 반드시 값을 v로 정해야 한다.

3. 일치성 (Agreement) : 모든 정상 프로세스들은 반드시 값이 일치한다.

무결성에 대한 정의는 적용 방법에 따라서 적절하게 변형될 수 있다. 예를 들어, 일부 정상 프로세스가 제안했던 값과 동일한 값으로 결정하는 더 약한 무결성은 모든 정상 프로세스들의 제안 값을 필요로 하지 않는다. 무결성(Integrity)은 이 분야에서 유효성 (Validity)로 알려져있다.^[1]

t개 이하의 실패에서 n개의 프로세스들 간의 합의를 정확하게 보장하는 프로토콜을 t-복원성(t-resilient) 프로토콜이라 부른다.

아래 두 가지 요소가 합의 프로토콜의 성능의 핵심 요소이다. 대문자 O 표기법으로 나타낸다.

• 실행 시간(running time) : 메시지 교환 라운드 수를 나타내는 함수이다.
• 메시지 복잡도(message complexity) : 프로토콜에 의해 생성된 메시지 트래픽 수를 나타내는 함수이다.

그 밖에도 메모리 사용량이나 메시지 크기 등이 성능 요인으로 포함된다.

비잔틴 장애를 허용하는 다항 시간 이진 합의 프로토콜의 예로는 Garay와 Berman에 의해 제안된 Phase King 알고리즘이 있다.

구글은 Chubby라고 불리는 분산 잠금 서비스 라이브러리를 구현했다.

비트코인은 P2P 네트워크에서 합의를 유지하기 위해 작업 증명을 사용하였다.

많은 P2P 온라인 실시간 전략 게임은 유저들 간에 게임 상태를 관리하기 위해 변형된 Lockstep 프로토콜을 합의 프로토콜로 사용한다.

• 비잔티움 장애 허용
• 상태 기계 접근법