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

비잔티움 장군 문제(비잔티움 장애 허용)란 레슬리 램포트와 쇼스탁, 피스가 공저한 1982년 논문에서 최초 사용된 표현이다.

가정 상황은 아래와 같다.

- 300 명의 병력이 있는 비잔티움 성을 100명씩의 병력을 가진 장군 5명이 치려고 한다.

- 이때 장군 5명은 모두 지리적으로 떨어져 있어, 연락병을 통해 소통이 가능하다.

- 이기려면 적 병력보다 많은 병력이 공격해야 한다.

- 장군들 중에는 배신자가 있어 서로 신뢰가 불가능하다.

문제) 서로 신뢰할 수 없는데, 어떻게 공격 시각을 합의 할 것인가?

- 공격 시간을 상관 없음, 다만 모두 한번에 일제히 공격할 수 있도록 합의된 시간이여야 함.

- 배신자는 병력이 모이면 곤란하므로, 이전 장군에게 받은 시간과 다른 시간을 제시함

- 각 장군은 자신의 가장 근처에 있는 장군에게만 연락할 수 있음.

- 배신자 또한 지정한 시간에 공격에 가담해야만 함.

이러한 상황에서 문제가 발생할 경우

장군 1 : 장군 2 에게 9시에 공격하자고 전달

장군 2 : 장군 3 에게 9시에 공격하자고 전달

장군 3 : 장군 4 에게 9시에 공격하자고 전달

장군 4(배신자) : 장군 5 에게 10시에 공격하자고 거짓 전달

장군 5 : 10시 공격이라는 것 인식

즉, 9시에 장군 1, 2, 3 만 공격하게 되어 비잔티움 성 수복 실패.

이러한 문제를 해결하기 위해서는 몇명의 신뢰성있는 장군이 필요한지와, 어떤 규칙으로 소통으로 해야하는 지에 대한 문제가 비잔티움 장군 문제(비잔티움 장애 허용)이다.

최근 비잔티움 장군 문제를 해결할 대안으로 떠오른 것이, 블록체인의 합의 수렴 알고리즘이다.

이는 블록체인 백과에서 자세히 다루도록 하겠다.