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

1 개요

Two Generals' Problem, Two Generals Paradox, Two Armies Problem, Coordinated Attack Problem

두 장군 문제, 두 장군 역설, 두 부대 문제, 협공 문제

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

2 상황

 

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

( 한쪽이 먼저 단독으로 공격하면 패배함 )

• 그래서 소통을 통해 공격시간을 합의하고 상대의 확답을 받아야 함
• 확답조차도 제대로 전달될지 확실하지 않으므로 완벽히 확신하려면 무한히 많은 메시지가 필요함

3 같이 보기

• 비잔틴 장군 문제
• 비잔틴 장애 허용

4 참고 자료

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