두 장군 문제, 비잔틴 장군 문제

1 개요

Two Generals' Problem

두 장군 문제

• 컴퓨터 과학 분야의 사고 실험
• 불확실한 연결 기반의 통신상황에서 동작을 동기화할 때의 함정, 설계 과제를 명시하기 위한 것
• 문제의 본질: 두 장군이 안전하게 합의할 수 있는 알고리즘을 설계하는 것이 불가능함

2 상황

 

• 두 장군이 각각 이끄는 두 부대 A1, A2가, 요새도시 B를 공격할 준비를 하고 있음
• 두 부대는 도시 근처의 두 언덕 뒤에 각각 진을 침
• 두 언덕은 계곡으로 나뉘어 있어, 소통하는 유일한 방법은 계곡을 통과하는 연락병을 보내는 것뿐임
• 불행히도 계곡에는 적군이 있어 연락병이 포획될 가능성이 있음
• 두 장군은 각각 언덕에 오르기 전에 공격하기로는 합의했으나 그 시각은 합의되지 않았음
• 공격이 성공하려면 동시에 도시를 공격해야만 함

( 한쪽이 먼저 단독으로 공격하면 병력부족으로 패배 )

• 그래서 소통을 통해 공격시간을 합의하고 그 합의를 상대가 인지했다는 것을 확인해야 함
• 인지확인 메시지조차도 제대로 전달될지 확실하지 않으므로 합의에 이르기 위해서는 무한히 많은 메시지가 필요함

3 참고 자료

• https://en.wikipedia.org/wiki/Two_Generals'_Problem