비잔틴 내결함성

비잔틴 장군 문제

비잔틴 내결함성

비잔틴 제국은 적군에게 함락된 도시를 포위하고 동시에 공격하여 탈환하려 합니다.


도시 주변에 포위된 모든 장군은 도시를 되찾기 위해 동시에 공격합니다.

모든 장군은 동시 공격이 탈환의 조건이라는 것을 알고 있습니다.


그러나 비잔티움 장군들은 그들 중 일부가 이미 적과 통신하고 있으며 서로 통신하는 메신저가 도시에서 나오는 정찰병에게 잡힐 수 있음을 알고있었습니다.

장군이 황제에게 충성하는 것인지 반역하려는 것인지 확실하지 않은 충성스러운 장군은 반역자가 자신의 군대를 사용하여 포위 공격을 깨거나 적에게 메시지를 전달할 수 있기 때문에 딜레마에 직면합니다.

충직한 장군은 사절의 명령에 충실히 복종하고 그 외에는 아무것도 하지 않는다.

그리고 간사한 장수들, 일부는 사절들에게 얽매이지 않고 마음대로 할 수 있는 장수들입니다.

이때 충신이 반역자가 있는 상황에서 동일한 공격을 계획할 수 있도록 하기 위해 얼마나 많은 충신이 필요한지, 그리고 장군들이 의사소통을 위해 어떤 규칙을 사용해야 하는지, 이것이 비잔틴 일반 문제입니다.

예를 들어 6군이 “금요일 오후 1시에 포위하라!
세 번째 장군.

하지만 4장군이 반역자라고 가정하면 토요일 오후 1시에 4장군이 적을 공격하고 5장군에게 포위를 약화시킨다!
메시지를 보낸 다섯 번째 장군은 여섯 번째 장군에게 메시지를 보냈고, 금요일 오후 1시, 전체 병력의 절반에 불과한 비잔틴 제국 군대는 도시 수비대에게 패배했습니다.

장군들은 이 참사를 해결하기 위해 배신자를 찾아내거나, 배신자가 배신자라면 알 수 없는 코드로 메신저를 보내거나, 동시에 여러 장군에게 메신저를 보내 명령을 확인하는 등 여러 가지 방법을 동원해야 했다.

.

이 방안이 타당한지 판단하는 것이 좋겠지만 우리가 판단할 수 없기 때문에 포기하고 다수의 합의를 얻는 데에만 집중하겠습니다.

보장해야 하는 것은 다음과 같습니다.


모든 충성스러운 장군은 동일한 정보에 접근할 수 있어야 합니다.

(배신자가 누군지 모르기 때문에 X 장군에게 직접 받아도 바로 사용할 수 없습니다.

)
n장군이 충신이면 n장군이 보낸 돈을 충신들에게 공평하게 보내야 한다.

비트코인 블록체인의 노드가 서로 정보를 비교하거나 시스템에 결함이 있는 프로그램이 있더라도 다른 프로그램이 버그를 우회할 수 있는 상황을 가정하는 데 도움이 됩니다.