친구에게 “내일 오후 3시에 역 앞에서 보자”라는 메시지를 보냈는데 답장이 오지 않으면, 상대가 메시지를 읽었는지 몰라 괜히 불안해집니다. 답장으로 “알겠어”가 와도 이번에는 그 답장을 내가 받았다는 사실을 상대가 아는지 궁금해질 수 있습니다. 컴퓨터 과학에는 이 끝없는 확인의 고리를 장군 두 명의 이야기로 풀어낸 유명한 문제가 있습니다. 바로 ‘두 장군 문제(Two Generals’ Problem)’입니다.

두 장군 문제란 쉽게 말해 ‘메시지가 중간에 사라질 수 있는 통신로로는 두 쪽이 같은 행동에 합의했다는 사실을 절대 완벽하게 확신할 수 없다’는 것을 보여 주는 사고 실험을 의미합니다. 네트워크와 분산 시스템을 처음 배울 때 빠지지 않고 등장하며, 컴퓨터 통신 문제 가운데 해결할 수 없다는 것이 처음으로 증명된 문제로 꼽힙니다.

본 자료에서는 두 장군 문제가 어떤 상황을 그리는지부터 왜 풀 수 없는지, 이 문제가 어디서 시작되었는지, 그리고 실제 기술이 이 한계를 어떻게 다루는지까지 차례로 살펴보겠습니다.

확인의 확인이 끝나지 않는 두 장군 문제

두 장군 문제는 어떤 상황일까

이 문제는 성을 사이에 둔 두 군대의 이야기로 시작합니다.

(1) 따로 진을 친 두 군대
두 장군이 이끄는 군대가 성 하나를 공격하려고 서로 다른 언덕에 진을 치고 있습니다. 두 군대가 동시에 공격하면 성을 함락할 수 있지만, 한쪽만 공격하면 그 군대는 크게 패하고 맙니다.

(2) 위험한 골짜기를 건너는 전령
두 장군이 연락할 방법은 성의 군대가 지키는 골짜기를 지나 전령을 보내는 것뿐입니다. 전령은 언제든 붙잡힐 수 있고, 보낸 쪽은 전령이 도착했는지 알 길이 없습니다.

(3) 장군들이 원하는 확신
장군들은 공격 시각을 정하는 데 그치지 않고, ‘우리 둘 다 그 시각에 공격한다’는 사실을 서로 확실히 알고 싶어 합니다. 이 확신이 있어야 마음 놓고 군대를 움직일 수 있기 때문입니다.

이처럼 두 장군 문제는 믿을 수 없는 통신로 위에서 두 쪽이 행동을 맞추려 할 때 생기는 어려움을 단순한 장면으로 압축해 보여 줍니다.

왜 끝내 확신할 수 없을까

전령을 여러 번 주고받으면 해결될 것 같지만, 확인을 늘릴수록 같은 고민이 반복될 뿐입니다.

(1) 첫 번째 메시지의 불안
첫 번째 장군이 “새벽 6시에 공격한다”는 전령을 보내도, 전령이 도착했는지 모르니 혼자 공격하게 될까 봐 망설이게 됩니다.

(2) 끝없이 이어지는 답장
두 번째 장군이 “받았다, 6시에 공격하겠다”는 답장을 보내면, 이번에는 두 번째 장군이 그 답장의 도착 여부를 걱정합니다. 첫 번째 장군이 답장을 받았다는 확인을 다시 보내도, 그 마지막 전령 역시 붙잡힐 수 있습니다.

(3) 마지막 전령의 역설
몇 번을 주고받든, 마지막으로 보낸 전령이 도착했는지를 보낸 쪽은 알 수 없습니다. 마지막 전령이 붙잡혀도 보낸 쪽이 보기에는 상황이 똑같으므로, 그 전령 하나에 공격 여부가 달린 방식이라면 한쪽만 공격하는 일이 생길 수 있습니다. 그래서 정해진 횟수로 확인을 주고받는 어떤 방법도 두 장군을 완벽하게 맞출 수 없다는 결론이 나옵니다.

핵심은 확인 메시지도 원래 메시지만큼 쉽게 사라질 수 있다는 점입니다. 확인을 아무리 겹겹이 쌓아도 맨 마지막 한 겹의 불확실성은 그대로 남습니다.

두 장군 문제는 어디서 시작되었을까

이 문제는 컴퓨터 네트워크가 막 발전하던 1970년대에 정리되었습니다.

• 처음 실린 논문(First Publication): 1975년 아코윤루(E. A. Akkoyunlu), 에카나담(K. Ekanadham), 후버(R. V. Huber)가 네트워크 통신 설계의 제약을 다룬 논문에서 이 문제와 해결할 수 없다는 증명을 처음 발표했습니다. 이 논문에서는 장군 대신 서로 연락하는 두 갱단 무리로 상황을 설명했습니다.
• 이름을 붙인 사람(Naming): 데이터베이스 연구자 짐 그레이(Jim Gray)가 1978년 데이터베이스 운영체제에 관한 글에서 이 문제를 ‘두 장군의 역설(Two Generals Paradox)’이라고 부르면서 지금의 장군 이야기로 널리 알려졌습니다.
• 더 큰 문제로의 확장(Byzantine Generals Problem): 1982년 레슬리 램포트(Leslie Lamport), 로버트 쇼스탁(Robert Shostak), 마셜 피스(Marshall Pease)는 여러 장군 가운데 배신자가 섞인 상황을 다룬 ‘비잔틴 장군 문제’를 발표했습니다. 두 장군 문제는 이 문제를 배우기 전 입문용으로 자주 소개됩니다.

실제 기술은 이 한계를 어떻게 다룰까

완벽한 확신이 불가능하다면, 현실의 기술은 불확실성을 없애기보다 감당할 만한 수준으로 줄이는 쪽을 택합니다.

(1) 여러 번 보내기
첫 번째 장군이 전령을 여러 명 보내면 모두 붙잡힐 확률은 크게 낮아집니다. 확신은 아니어도 성공 가능성을 충분히 높일 수 있습니다.

(2) 확인과 재전송
인터넷의 기본 통신 규약인 TCP(Transmission Control Protocol)는 연결을 맺을 때 세 번의 메시지를 주고받고, 데이터를 보낸 뒤 받았다는 확인이 정해진 시간 안에 오지 않으면 다시 보냅니다. 이 방식도 양쪽 상태가 언제나 같다고 보장하지는 못하지만, 실제로 쓰기에 충분한 신뢰를 만들어 냅니다.

(3) 침묵도 신호로 쓰기
일정 시간 동안 아무 연락이 없으면 상대가 계획을 받아들였다고 미리 약속해 두는 방법도 있습니다. 전령을 덜 보내면서도 높은 확신을 얻을 수 있습니다.

이런 방식들은 모두 완벽함 대신 ‘충분히 믿을 만함’을 목표로 삼는다는 공통점이 있습니다.

두 장군 문제는 아무리 정교한 기술도 불확실한 통신로의 한계를 완전히 넘을 수는 없다는 사실을 일깨워 줍니다. 오늘날 우리가 쓰는 메신저와 결제 시스템, 클라우드 서비스도 이 한계를 인정한 위에서 설계됩니다.

완벽한 확신이 불가능하다는 사실을 받아들이고 그 위에 안전장치를 쌓는 것, 그것이 믿을 수 있는 시스템 설계의 첫걸음입니다.