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

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

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

Byzantine Generals Problem

비잔틴 장군 문제, 비잔틴 장군의 딜레마

1 두 장군 문제

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

1.1 상황

 

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

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

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

2 비잔틴 장군 문제

• 두 장군 문제를 일반화한 문제

2.1 상황

• 비잔틴 제국의 여러 장군들이 하나의 적군 도시를 공격하기 위해 출병함
• 적은 매우 강해서 과반수 이상의 장군들이 같은 시각에 공격해야만 승리하고, 그렇지 않으면 패배
• 모든 장군들간의 소통은 연락병 보내는 방법 밖에 없음
• 장군들 중에는 배신자가 있을 수 있어서 서로 신뢰할 수 없음

( 배신자는 가짜 공격 명령을 보낼 수도 있음 )

• 서로 신뢰할 수 없는데 공격시각을 어떻게 합의할까?

3 같이 보기

• 비잔틴 장애 허용
• 작업 증명 체계
• 블록체인
• 비트코인
• 비잔틴

4 참고

• https://en.wikipedia.org/wiki/Two_Generals'_Problem
• http://navercast.naver.com/contents.nhn?rid=122&contents_id=57231