일부 노드가 비정상적으로 작동 할때, 과연 모든 노드가 같은 장부를 가질 수 있을까?

비잔틴 문제

---

비잔틴(Byzantine) : 임의의 행동을 하는 노드를 비잔틴이라고 부른다.

비잔티움 장군 문제에서 용어를 가지고 온 것

비잔티움 장군문제

• 적군이 300명이고, 아군이 500 명이라고 하자.
• 각 부대는 100명씩 나뉘어져 5개로 나누어져 있고, 모든 부대가 같은 날 같은 시각에 적군을 공격하려고 한다.
• 각 부대는 물리적으로 지금 멀리 떨어져 있는 상황이므로, 공격 날짜와 시각을 받은 사람이 가까운 사람한테 알려준다.

여기서 적과 내통하는 부대가 존재하여 잘못된 정보와 원래 정보가 같이 퍼져나간다면, 이 전쟁에서 승리할 수 있는가?
이것이 비잔티움 장군 문제이다.


여기서,
전체 참여하는 부대 수 : 전체 분산 시스템을 구성하고 있는 노드 수
적과 내통하는 부대의 수: 비잔틴으로 임의로 행동하는 노드의 수

이를 바탕으로 분산시스템에서는 어떻게 합의에 도달할 수 있을까에 대하여 고민해 볼 수 있다.

비잔틴 동의

---

참여 노드 2개

먼저 특정 내용에 대해 합의를 하려면 일반적으로 찬성/반대 두가지가 존재한다. 따라서 서로 의견의 다를 경우 합의에 도달할 수 없다.

참여 노드 3개

• 노드 A,B,C 가 있고 C 는 비잔틴
• 찬성은 O, 반대는 X
• A,B,C 각자 투표를 진행 후 자신을 제외한 다른 두 명에게 자신의 결과를 알려준다.

비잔틴 C는 A,B에게 서로 다른 결과를 알려주어 A,B 에게 문제가 생긴다.

A: AX BO CO
B: AX BO CX

여기서 보면 C 가 비잔틴 임을 알수 있다. 그러나 C까지 보면

A: AX BO CO
B: AX BO CX
C: AX BX CO

누가 비잔틴인지 알 수 없다.

비잔틴 동의

비잔틴 동의는 이를 n 개로 확징시켜서 판단한다.

n개의 노드를 가진 시스템에서 비잔틴의 수는 3분의 n보다 크거나 같다면, 비잔틴 동의를 할 수 없다.

다시말해

n 개의 노드를 가진 시스템에서 f >= n/3 비잔틴 노드와 비잔틴 동의를 할 수 없음

위의 예시에서 n=3 인 경우, 비잔틴 노드 f 가 f >= 1 인 경우 비잔틴 동의를 할 수 없기 때문에 불가 했던 것
n = 4 이라면, f >= 4/3 인 경우에 합의가 불가능 하기 때문에 비잔틴이 1명 있어도 합의가 가능하다.