두 장군의 문제(Two Generals Problem)

 

두 장군의 문제(Two Generals Problem)는 1972년 등장한 일종의 가상 실험이다.
(유사한 문제가 포함된 기술로 1969년 창설된 '알파넷 ARPA(The Advanced Research Project Agency)net')

출처: https://haydenjames.io

 

이 실험에서 가정 조건

- 두 아군 부대의 장군 A와 B가 적군이 점령한 도시 양옆에 주둔한 상황이다.
- 두 장군은 적군을 점령하기 위해 두 부대가 동시(같은 날, 같은 시각)에 공격하려 한다.
- 동시에 공격하지 않으면 이길 수 없다. 한쪽만 공격하면 안 된다.
- 공격 연락을 담당하는 연락병은 직접 적군의 도시를 통과해야 한다. 이러한 연락병이 가진 메시지는 항상 적군에게 뺏길 위험이 존재한다는 가정하에 진행이 된다.

 

문제의 상황

장군 A는 B에게 메시지를 보냈지만 잘 전달됐는지 확신을 하지 못한다.
이에 B가 메시지를 잘 받았으면 A에게 확인 답장을 보내야 하는데 B도 마찬가지로 이 메시지가 A에게 무사히 도달했는지 자신하지 못한다.
이에 B를 안심시키고 함께 공격하기 위해 A가 답장을 받았다고 재 답장을 해야 하지만 이 역시 B에게 잘 도달했는지 장담하지 못한다.
결국 이는 두 장군이 같은 수준의 합의에 도달할 수 없고 이러한 불확실성은 결국 함께 적군의 도시를 공격할 수 없다는 의미이다. 이후 이 문제는 실제로 해결할 수 없는 것으로 증명됐으며 비트코인으로 치면 잠재적인 배신자들이 섞여 있는 한 참여자들은 같은 내용의 거래기록을 갖는 데까지 도달하지 못한다는 의미이다.

 

참고

비잔티움 장군 문제(Byzantine Generals Problem)

비잔티움 장애 허용(Byzantine Fault Tolerance)