비잔틴 장군 문제란 무엇인가?

비잔틴 장군 문제 (Byzantine General's Problem)는 실제 있었던 일이 아니라 컴퓨터 공학에서 만든 가상의 문제이다.

비잔틴 장군들이 적군을 공격하기 위해 서로 합의를 하는 문제로 장군들은 지리적으로 멀리 떨어져 있고 다음의 2가지를 가정한다.

1. 장군들 중 배신자가 있다.

2. 장군들 사이에 메세지를 전하는 전령이 문제가 생겨 죽을 수도 있고 도중에 메세지가 위조될 수도 있다.

비잔틴 장군 문제는 이와 같은 상황에서 배신자가 아닌 충직한 장군들끼리 다수결의 결과를 정확하게 구하는 방법에 대한 문제이다.

예를 들면, 5명의 장군이 있고 그 중 1명의 배신자가 있을 때 충직한 4명의 장군 중 2명은 공격에 투표하고 나머지 2명은 후퇴에 투표하여 자신의 결정을 모든 장군들에게 전령을 통해 메세지를 전달했을 때, 1명의 배신자 장군이 공격에 투표한 장군에게는 자신도 공격에 투표했다고 전달하고 후퇴를 결정한 장군에게는 자신도 후퇴에 투표했다고 전달하면, 2명의 장군은 공격하고 2명의 장군은 후퇴하게 된다. 이에 따라 동시에 공격을 하지 못해 아군에게 큰 피해를 볼 수 있다.

이와 같은 비잔틴 장군 문제에서 합의 결과를 정확하게 아는 방법은 1982년 처음 발견되었고 1999년 보다 효율적인 방법이 발견되었다. 1999년 MIT에서 발견한 비잔틴 장군 문제의 해결은 여기에서 논문을 볼 수 있다.

비잔틴 장군 문제는 중앙의 서버가 없는 비트 코인에서 부정 행동을 막는데 사용되고 보잉 777과 787 항공기의 컴퓨터 시스템에서 고장난 시스템에 의한 오동작을 막는데 사용된다.

컴퓨터 공학에서는 비잔틴 장군 문제와 같은 식의 비유를 사용하는 경우가 많다. (식사하는 철학자 문제)

@ 비트코인의 쉬운 이해