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

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

'비잔티움 장군 문제(Byzantine Generals Problem)'로부터 파생된 장애 허용 분야 연구의 한 갈래다.

 

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

비잔티움 제국이 적이 점령중인 도시를 포위하였고, 동시 공격으로 탈환하려 한다.
도시 주변을 포위한 각 장군들의 동시 공격으로 도시를 탈환할 수 있다. 각 장군들은 동시 공격해야 탈환 가능한 조건임을 알고 있다.
그러나 비잔티움의 장군들은 자신들 중 몇몇이 이미 적과 내통하고 있음과 서로에게 연락할 전령들이 도시에서 나온 척후대에게 사로잡힐 수 있는 것도 알고 있다.


어떤 장군이 황제에게 충성스러운지, 혹은 모반을 하려는지 확실하지 못한 상황에서 충성스러운 장군들은 배신자들이 병력을 물려 공성을 방해하거나 적에게 소식을 넘길수 있다는 상황 때문에 딜레마에 빠진다.

충직한 장군들은 전령들이 보낸 명령을 충실하게 따르며 이 외의 행동은 하지 않는다. 그러나 전체 장군 중 일부인 배신자 장군들은 전령에 얽매이지 않고 마음대로 행동할 수 있다. 이 때 배신자의 존재에도 불구하고 충직한 장군들이 동일한 공격 계획을 세우기 위해서는 충직한 장군들의 수가 얼마나 있어야 하며, 장군들이 어떤 규칙을 따라 교신해야 하는지에 대한 문제가 바로 비잔티움 장군 문제다.

예를 들어 여섯개의 부대가 한꺼번에 금요일 오후 1시에 도시를 공성한다!라는 전략을 전달한다려 한다면, 첫번째 장군이 두번째 장군에게, 그 명령을 들은 두번째 장군이 세번째 장군에게 같은 내용을 담은 전령을 보낸다.

그러나 네번째 장군이 배신자인 상황을 가정했을 때, 네 번째 장군은 공성을 약화시키기 위해 다섯번째 장군에게 토요일 오후 1시에 적을 공격한다! 라는 전갈을 보낸다. 충성스러운 다섯번째 장군은 이를 그대로 여섯번째 장군에게 보내고, 금요일 오후 1시에는 전체 병력의 절반밖에 나오지 않은 비잔티움 제국의 군대는 도시 방어군에게 참패하게 된다.

이러한 참사를 해결하기 위해 장군들은 배신자를 찾아내거나, 배신자라면 알 수 없는 암호를 통해 전령을 보내거나, 여러 장군들에게 한꺼번에 전령을 보내 명령을 대조해보는 등 여러 방법을 사용해야만 한다.



계획이 합리적인지도 판단한다면 더 좋으나, 이는 판단할 수 없으므로 포기하고, 오직 다수의 합의를 이끌어내는 것에만 초점을 맞춘다.

보장해야 하는 것은 아래와 같다.
모든 충직한 장군들은, 같은 정보를 획득해야 한다. (누가 배신자인지 모르기 때문에, x번째 장군이 직접 보낸 메시지를 받았다 하더라도, 바로 사용할 수 없다.)
만약 n번째 장군이 충직하다면, n번째 장군이 보낸 값은 충직한 장군들한테 같게 보내져야 한다.


이는 비트코인 블록체인의 노드들이 서로간의 정보를 대조하거나, 시스템 상 오류가 있는 프로그램들이 있어도 타 프로그램들이 오류를 우회할 수 있는 상황을 가정하는 데에 도움을 준다.