Two Generals Problem이란?
Two Generals Problem(두 장군 문제)은 신뢰할 수 없는 통신 채널을 통해 두 주체가 완벽하게 동일한 결론에 도달할 수 있는지를 다루는 컴퓨터 과학의 고전적인 사고 실험입니다. 분산 시스템에서 ‘메시지 전달이 100% 보장되지 않는 상황’에서 완벽한 합의(consensus)가 근본적으로 불가능하다는 것을 증명하기 위해 만들어졌습니다.
상황은 이렇습니다. 두 장군이 각각 다른 언덕에서 적의 도시를 포위하고 있습니다. 두 부대가 ‘동시에’ 공격해야만 승리할 수 있고, 한쪽만 공격하면 전멸합니다. 두 장군은 오직 전령을 통해서만 메시지를 주고받을 수 있는데, 이 전령이 적에게 붙잡혀 죽을 수도 있는 위험한 통신 채널을 지나야 합니다.
왜 완벽한 합의가 불가능한가
장군 A가 ‘내일 새벽 6시에 공격하자’는 메시지를 보냈다고 가정해봅시다. 전령이 무사히 도착해서 장군 B가 메시지를 받았습니다. 하지만 장군 A는 자신의 메시지가 잘 전달됐는지 확신할 수 없습니다. 그래서 장군 B는 ‘알겠다’는 확인 메시지를 다시 보냅니다.
문제는 여기서 끝나지 않습니다. 장군 A 역시 이 확인 메시지가 무사히 도착했는지 알 수 없기 때문에, 또 다시 확인의 확인을 보내야 합니다. 이 과정은 논리적으로 무한히 반복됩니다. 어느 시점에서든 마지막 메시지가 상대에게 도착했다는 것을 100% 확신할 방법이 없기 때문입니다. 결국 두 장군은 ‘유한한 메시지 교환’만으로는 서로가 같은 결정을 내렸다는 것을 수학적으로 완벽히 보장할 수 없습니다. 이것이 이 문제의 핵심 결론입니다.
실무에서의 의미와 대응 방법
이 문제는 분산 시스템, 네트워크 프로토콜, 데이터베이스 트랜잭션 설계에서 매우 중요한 이론적 배경이 됩니다. 예를 들어 TCP의 3-way handshake도 이 문제를 완벽히 해결하는 것이 아니라, 현실적으로 ‘충분히 신뢰할 수 있는’ 수준까지 실패 확률을 낮추는 방식으로 설계되어 있습니다.
실무에서는 완벽한 합의 대신 다음과 같은 현실적 전략을 사용합니다.
- 타임아웃과 재전송(retry)을 통한 확률적 신뢰성 확보
- 멱등성(idempotency)을 보장해 중복 메시지가 와도 안전하게 처리
- 2단계 커밋(2PC), 3단계 커밋(3PC) 등 분산 트랜잭션 프로토콜 활용
- 합의 알고리즘인 Paxos, Raft를 통해 다수결 기반의 실용적 합의 달성
즉, Two Generals Problem은 ‘완벽’은 불가능하지만 ‘충분히 안전한 수준’은 공학적으로 달성 가능하다는 것을 알려주는 이론적 토대입니다. 분산 시스템을 설계할 때 왜 재시도 로직과 타임아웃 처리가 필수적인지 이해하는 데 핵심이 되는 개념이라고 할 수 있습니다.