비잔틴 장군 문제

여러 컴퓨터가 힘을 합쳐야 하는데, 그중 일부가 고장이 아니라 거짓말을 한다면? 단순히 멈추는 노드와, 일부러 서로 다른 정보를 흘리는 노드는 완전히 다른 문제다. 비잔틴 장군 문제는 이런 "악의적인 참여자가 섞여 있어도 나머지가 합의에 이를 수 있는가"를 다루는 분산 컴퓨팅의 고전 난제다.

이야기 — 비잔틴 제국의 장군 여러 명이 각자 군대를 이끌고 적의 도시를 포위했다. 총공격이 성공하려면 모든 장군이 같은 시각에 같은 행동(전원 공격 또는 전원 퇴각)을 해야 한다. 장군들은 전령을 보내 서로 의견을 주고받는데, 그중 몇 명은 배신자다. 배신자는 어떤 장군에게는 "공격"을, 다른 장군에게는 "퇴각"을 보내 혼란을 일으킨다. 배신자가 있어도 충성스러운 장군들끼리는 항상 같은 결론에 도달하게 만들 수 있을까?

1. 충돌 상황 직접 만들어 보기

지휘관(보라색, 중앙 원)이 장군들에게 명령을 내린다. 원 위의 장군 중 일부는 배신자로 설정할 수 있다. 배신자는 받은 명령을 그대로 전달하지 않고 옆 장군에게 다른 명령을 속삭인다. "명령 전송"을 누르면 각 장군이 최종적으로 다수결로 무엇을 결정하는지 확인해 보자.

장군 수 (지휘관 제외) 배신자 수 (f)

● 지휘관 (Commander) ● 충성 장군 (Loyal) — 클릭해서 배신자로 전환 가능 ● 배신자 (Traitor) — 공격 메시지 / 퇴각 메시지 (배신자의 거짓 전달)

충성 장군 전원 합의 여부

–

필요 조건 n ≥ 3f+1

–

현재 n / f

–

힌트: 장군 수를 3, 배신자를 1로 두면(n=3 < 3f+1=4) 배신자 단 1명만으로도 충성 장군끼리 서로 다른 결정을 내리게 된다. 장군 수를 6~9로 늘리면 같은 배신자 수라도 다수결이 안정된다.

2. 왜 하필 `n ≥ 3f+1`인가

전체 참여자(지휘관 포함) 수를 n, 배신자 수를 f라 하자. 각 장군은 다른 모든 장군에게서 받은 명령을 모아 다수결로 최종 행동을 정한다. 문제는 배신자가 서로 다른 사람에게 다른 말을 할 수 있다는 것이다. 최악의 경우 지휘관 자신이 배신자라면, 배신자는 자기 편(다른 배신자)과 짜고 "충성 장군들의 표를 정확히 절반씩 갈라놓을 정도"의 거짓 정보를 뿌릴 수 있다. 이를 막으려면 충성 장군의 수가 배신자 수보다 절대적으로 많아야 하고, 수학적으로 정리하면 n ≥ 3f+1, 즉 배신자는 전체의 3분의 1 미만이어야 한다는 조건이 나온다.

전체 n	배신자 f	3f+1	합의 가능?
3	1	4	불가능 — n < 3f+1
4	1	4	가능 — 경계값 충족
6	2	7	불가능 — n < 3f+1
7	2	7	가능 — 경계값 충족
10	3	10	가능 — 경계값 충족

직관 — 지휘관이 배신자라면, 절반의 충성 장군에게는 "공격 A"를, 나머지 절반에게는 "공격 B" 신호로 오인하게 만드는 메시지를 보내려 시도한다. 나머지 충성 장군들이 서로 메시지를 교차 확인(전달·재전달)해 다수결로 걸러내려면, 배신자가 아무리 애써도 충성 장군의 표가 배신자의 표보다 항상 많아야 한다. 참여자를 늘릴수록 배신자 비율이 낮아져 다수결이 버텨낸다 — 반대로 배신자 비율이 1/3을 넘으면 어떤 알고리즘으로도 구제 불가능하다는 것이 증명되어 있다(불가능성 정리).

3. 크래시 장애와 무엇이 다른가

Raft 같은 합의 알고리즘은 노드가 멈추거나 응답을 안 하는 것(crash fault)만 가정한다. 죽은 노드는 조용히 사라질 뿐 거짓말은 하지 않는다. 그래서 과반수, 즉 n ≥ 2f+1만 있으면 충분하다. 반면 비잔틴 장애는 노드가 살아서 의도적으로 서로 다른 거짓 정보를 퍼뜨릴 수 있다고 가정한다. "거짓말을 하는 두 번째 배신자를 걸러내기 위한 여유분"이 하나 더 필요해서 n ≥ 3f+1로 조건이 더 엄격해진다.

	장애 모델	필요 조건	예시
크래시 장애	멈춤·응답 없음만 발생	`n ≥ 2f+1`	Raft, Paxos
비잔틴 장애	거짓·모순된 메시지 전송 가능	`n ≥ 3f+1`	PBFT, 블록체인 합의

4. 의사코드 — 다수결로 배신자 걸러내기

def decide(my_id, received_orders):      # received_orders: {보낸이: 명령}
    counts = {}
    for sender, order in received_orders.items():
        counts[order] = counts.get(order, 0) + 1

    # 가장 많이 받은 명령을 최종 결정으로 채택
    majority_order = max(counts, key=lambda o: counts[o])
    return majority_order

# n >= 3f+1 이 보장되면, 배신자가 아무리 메시지를 조작해도
# 충성 장군들이 이 함수로 계산한 majority_order는 서로 전부 일치한다.

실제 비잔틴 합의 프로토콜(OM(f) 알고리즘, PBFT 등)은 여기에 여러 라운드에 걸친 재전송과 서명 검증을 더해, 배신자가 "누구에게 무엇을 보냈다"를 나중에 부인하거나 위조하지 못하게 막는다.

5. 어디에 쓰이나

블록체인 합의 — 채굴자·검증자 중 일부가 악의적으로 이중 지불을 시도해도 네트워크가 하나의 장부에 합의해야 한다. 작업 증명(PoW)과 PBFT 계열 알고리즘 모두 비잔틴 내결함성을 목표로 설계된다.

항공기·우주선 비행 컴퓨터 — 보잉 787, 스페이스 셔틀 등은 동일한 계산을 하는 컴퓨터 여러 대를 두고 다수결로 최종 명령을 정한다. 센서 오작동으로 컴퓨터 한 대가 엉뚱한 값을 계속 내보내도 나머지가 걸러낸다.

허가형 분산 원장(PBFT) — 하이퍼레저 패브릭 등 참여자가 정해진 컨소시엄 블록체인은 실용적 비잔틴 내결함성(Practical BFT)으로 초당 수천 건의 합의를 처리한다.

관련 개념 — 크래시 장애만 다루는 Raft 합의, 위·변조 탐지에 쓰이는 머클 트리와 함께 보면 분산 시스템의 신뢰 문제를 한눈에 비교할 수 있다.