컨텍스트 엔지니어링 실패모드 위키

합의 알고리즘 — 비잔틴 내성·정족수의 LLM 적용과 한계

22 min read

상위: 07_00_MOC

합의 알고리즘 — 비잔틴 내성·정족수의 LLM 적용과 한계

한 줄 정의

합의 알고리즘(consensus algorithm) 은 일부 노드가 고장 나거나(crash) 악의적으로 거짓을 말해도(Byzantine) 정직한 노드들의 정족수(quorum)가 단일한 값에 동의하도록 보장하는 분산 시스템 프로토콜이다. 멀티에이전트 LLM이 룰·기준 충돌에 빠졌을 때 “다수결·투표·반복토론으로 해소한다”는 발상의 이론적 뿌리이기도 하다. 다만 LLM 에이전트는 분산 합의가 전제하는 결정적·독립적 노드가 아니므로, 이 알고리즘들은 직접 이식이 아니라 은유와 부분 차용으로만 쓸 수 있다.

왜 중요한가

07_07-충돌해소와-합의-안전성-비합성성은 충돌을 탐지하고 우선순위로 해소 하는 절차(SCF의 Policy-Authority-Temporal)를 다뤘다. 그런데 우선순위로도 풀 수 없는 경우, 가령 동등한 권위의 에이전트 둘이 서로 다른 답을 우긴다거나 그중 하나가 01 오염된 출처 때문에 거짓을 확신할 때, 실무는 본능적으로 “여럿에게 물어 다수결로 정하자”로 흐른다. 멀티에이전트 디베이트(multi-agent debate), 셀프-컨시스턴시 투표, LLM 앙상블이 모두 이 직관의 변주다.

문제는 이 직관이 45년간 다듬어진 분산 합의 이론과 충돌한다는 점이다. 분산 합의는 “노드가 거짓말을 해도 안전하려면 정족수가 얼마여야 하나”를 정량적으로 답했고(PBFT의 n≥3f+1), 동시에 “다수가 곧 진실은 아니다”라는 한계도 분명히 했다. AI 강사·AX 컨설턴트에게 이 챕터가 주는 효용은 두 가지다. 하나는 고객이 “에이전트 3개 돌려서 다수결 하면 안전하죠?”라고 물을 때 왜 그것이 안전을 보장하지 않는지를 비잔틴 모델로 설명할 수 있다는 것이고, 다른 하나는 그럼에도 투표·디베이트가 실측에서 효과를 보이는 조건(다양성, 적은 라운드, 작업 유형)을 근거와 함께 처방할 수 있다는 것이다.

1. 분산 합의의 기초 — 정족수와 비잔틴 장애

1.1 두 종류의 장애 모델

분산 합의 이론은 노드가 망가지는 방식을 둘로 나눈다.

  • 크래시 장애(crash / fail-stop) — 노드가 멈추거나 응답하지 않는다. 단, 거짓말은 하지 않아서 멈추기 전까지 보낸 메시지는 정직하다. Paxos·Raft가 이 모델을 다룬다.
  • 비잔틴 장애(Byzantine fault) — 노드가 임의로 행동한다. 모순된 값을 서로 다른 노드에 보내거나, 의도적으로 거짓을 퍼뜨리거나, 프로토콜을 위반한다. 악의적 공격자와 버그, 오염을 모두 포괄한다. PBFT가 이 모델을 다룬다.

LLM 에이전트의 충돌은 비잔틴 모델에 가깝다. 01 오염된 에이전트는 멈추는 게 아니라 확신에 차서 거짓을 말하기 때문이다. 그래서 다수결을 논하려면 크래시(Raft)가 아니라 비잔틴(PBFT) 쪽 산수를 봐야 한다.

1.2 정족수(quorum) — 다수결의 정확한 산수

정족수 는 결정을 확정하려면 동의해야 하는 최소 노드 수다. 핵심 성질은 임의의 두 정족수가 반드시 겹친다(quorum intersection)는 것이다. 이 교집합이 “한 결정이 내려진 뒤 모순된 다른 결정이 동시에 내려질 수 없음(safety)“을 보장한다.

  • 크래시 모델(Raft/Paxos): 총 n개 노드 중 과반수(majority, ⌊n/2⌋+1)가 정족수다. n=2f+1이면 f개 크래시까지 견딘다(5개 중 2개가 죽어도 3개로 진행). 두 과반수는 반드시 1개 이상 겹친다.
  • 비잔틴 모델(PBFT): 거짓말하는 노드가 있으므로 과반수로는 부족하다. PBFT는 n ≥ 3f+1을 요구하고, 정족수 크기는 2f+1이다.

“pBFT satisfies safety and liveness if and only if n ≥ 3f + 1 … The protocol operates by forming quorums of size 2f + 1.” — Castro & Liskov 요약(OSDI 1999)

직관은 이렇다. f개가 거짓말을 할 수 있다고 하자. 두 정족수(각 2f+1)의 교집합은 최소 f+1개이고 그중 거짓 노드는 최대 f개이므로, 교집합에는 정직한 노드가 적어도 1개 남는다. 이 1개가 두 결정의 모순을 막는다. 그래서 비잔틴 1명을 견디려면 노드가 최소 4개 필요하다(3·1+1=4). 흔히 말하는 “에이전트 3개 다수결”은 비잔틴 1명조차 못 견디는 구성이라는 뜻이다.

graph TD
  Q["정족수 교집합 원리<br/>(quorum intersection)"]
  CR["크래시 모델 (Raft/Paxos)<br/>n = 2f+1 · 정족수 = 과반수<br/>f개 멈춰도 안전"]
  BY["비잔틴 모델 (PBFT)<br/>n = 3f+1 · 정족수 = 2f+1<br/>f개 거짓말해도 안전"]
  Q --> CR
  Q --> BY
  BY --> K["함의: 거짓 1명 견디려면<br/>노드 최소 4개<br/>('에이전트 3 다수결'은 부족)"]
  style Q fill:#FF8800,color:#fff
  style BY fill:#FF4444,color:#fff
  style K fill:#4488FF,color:#fff

1.3 PBFT의 3단계 프로토콜

PBFT(Castro & Liskov, 1999)는 비동기 네트워크에서 비잔틴 내성 상태기계 복제를 실용적 성능으로 달성한 최초의 알고리즘이다. 한 클라이언트 요청이 다음 3단계를 거친다.

  1. Pre-prepare — 현재 리더(primary)가 요청에 순번을 매겨 모든 백업에 전파한다.
  2. Prepare — 백업들이 그 순번에 동의하면 서로 prepare 메시지를 방송한다. 일치하는 prepare를 2f개 모으면 순서에 합의한 것으로, 같은 순번에 다른 값이 들어오지 못함을 보장한다.
  3. Commit — 노드들이 commit 메시지를 방송한다. commit이 2f+1개 모이면 실행·응답하고, 클라이언트는 일치하는 응답을 f+1개 받으면 결과를 확정한다.

핵심은 리더가 거짓말을 해서 순번을 잘못 부여해도 백업들의 정족수 합의가 그것을 거부한다는 점이다. 리더는 편의를 위한 존재일 뿐 권위의 단일점이 아니다. 이 설계는 07_05-메모리계층과-권한-MemGPT-오케스트레이터-워커의 “오케스트레이터가 틀려도 워커 검증이 잡는다”는 발상과 구조적으로 닮았다.

1.4 Raft — 이해 가능한 합의

크래시 모델만 다루면 산수가 훨씬 단순해진다. Raft(Ongaro & Ousterhout, 2014)는 Paxos와 동등한 결과를 내되 이해 가능성(understandability)을 설계 목표로 삼아, 합의를 리더 선출과 로그 복제, 안전성으로 분리했다.

“Raft produces a result equivalent to (multi-)Paxos and is as efficient as Paxos, but its structure is different … this makes Raft more understandable.” — Ongaro & Ousterhout(2014)

Raft의 교훈 중 LLM에 곧장 쓸 만한 것은 “과반수가 살아 있으면 시스템은 진행한다”는 가용성 모델과, 단일 리더가 충돌을 직렬화한다는 점이다. 07_03-공유-vs-격리-컨텍스트-트레이드오프의 Cognition “단일 선형 스레드” 처방이 사실상 Raft의 단일 리더 직렬화와 같은 철학을 담고 있다. 합의 비용을 치르느니 한 명이 순서를 정하라는 것이다.

2. LLM 에이전트로의 적용 — 투표·디베이트·합의

분산 합의를 그대로 못 쓰는 이유는 3절에서 짚고, 여기서는 부분 차용이 실제로 효과를 본 사례를 본다.

2.1 멀티에이전트 디베이트(Multi-Agent Debate)

Du et al.(2023, MIT)의 디베이트는 여러 LLM 인스턴스가 각자 답과 추론을 내고 여러 라운드의 토론을 거쳐 공통 답으로 수렴시킨다.

“multiple language model instances propose and debate their individual responses and reasoning processes over multiple rounds to arrive at a common final answer.” — Du et al.(2023)

논문은 수학·전략 추론과 사실성을 유의하게 개선하고 환각과 오답을 줄였다고 보고한다(구체적 수치는 본문 표 참조). 메커니즘은 합의 알고리즘과 다르다. 정족수 투표가 아니라, 에이전트가 서로의 추론을 읽고 의견을 갱신하는 심의(deliberation)에 가깝다.

2.2 투표 vs 합의 — 어느 결정 프로토콜이 나은가

Kaesberg et al.(ACL 2025 Findings, “Voting or Consensus?“)은 디베이트의 결정 프로토콜 자체를 비교했다.

“voting protocols improve performance by 13.2% in reasoning tasks, while consensus protocols by 2.8% in knowledge tasks.” — Kaesberg et al.(2025)

결정 프로토콜강점 작업개선폭
투표(voting)추론(reasoning)+13.2%
합의(consensus)지식(knowledge)+2.8%
에이전트 수 ↑전반향상
토론 라운드 ↑ (투표 전)—성능 저하

핵심 처방은 두 가지다. 하나는 작업 유형이 변수라는 것이다. 추론에는 투표, 지식에는 합의가 낫다. 다른 하나는 투표 전에 라운드를 늘리면 오히려 나빠진다는 것이다. 토론을 오래 할수록 다양성이 죽기 때문인데, 이는 곧 동조 압력 문제와 직결된다.

2.3 다수결의 함정 — 동조 압력(conformity)

투표가 효과적이려면 표들이 독립적이어야 한다. 비잔틴 모델이 정직 노드의 독립성을 가정하는 것과 같은 이치다. 그런데 LLM 에이전트는 서로의 출력을 읽으면서 빠르게 동조한다. 디베이트 연구들이 입을 모아 내놓는 경고는 다음과 같다.

  • 에이전트들은 합의 답(consensus answer)으로 빠르게 의견을 바꾼다. 정확할 때는 좋지만, 틀린 다수에 정답인 소수가 끌려가면 독립적 정정(independent correction)이 억제된다.
  • 다수 압력이 독립적 정정을 억누른다(majority pressure suppresses independent correction).
  • 성공의 지배 요인은 순서나 신뢰도 공개 같은 구조 파라미터가 아니라 내재적 추론 강도와 집단 다양성(group diversity)이다.

결국 LLM 다수결은 분산 합의가 보장하는 안전성을 갖지 못한다. 표가 독립이 아니라 서로 상관되어 있어, 공통 오염원 하나가 다수를 동시에 틀리게 만들 수 있다. 이것이 07_06-provenance와-신뢰등급-프로베넌스-역설의 “자기보고가 오염을 확산”과 같은 병리의 투표 버전이다.

graph LR
  subgraph BFT["비잔틴 합의 (이상)"]
    I1["정직 노드<br/>독립적 판단"] --> QV["정족수 교집합이<br/>정직성 보장"]
  end
  subgraph LLM["LLM 다수결 (현실)"]
    A1["에이전트들이<br/>서로 출력 읽음"] --> CONF["동조 압력<br/>표가 상관됨"]
    CONF --> RISK["공통 오염원 1개가<br/>다수를 동시 오류로"]
  end
  style QV fill:#44AA44,color:#fff
  style RISK fill:#FF4444,color:#fff

3. 왜 분산 합의를 그대로 못 쓰는가 — LLM은 결정적 노드가 아니다

분산 합의의 안전성 증명은 노드에 대한 가정 위에 선다. LLM 에이전트는 그 가정들을 거의 모두 위반한다.

분산 합의의 가정LLM 에이전트의 현실결과
결정성 — 같은 입력 → 같은 출력샘플링·온도로 비결정적, 같은 프롬프트도 답이 흔들림”동일 상태” 정의가 불가능 → 상태기계 복제 전제 붕괴
고장은 f개로 한정공통 학습편향·공통 오염원이 상관된 다수 오류 유발”f개 비잔틴” 가정이 깨짐 → 정족수 산수 무력화
표의 독립성에이전트가 서로 출력을 읽고 동조다수결이 독립 표본이 아님 → 안전성 미보장
검증 가능한 정체성·서명한 모델 복제본은 “독립 노드”가 아님4개 인스턴스가 사실상 1개 의견일 수 있음
명확한 결정값자연어 답은 동치 판정조차 모호(“같은 답”인가?)정족수 일치 판정 자체가 LLM 판단에 의존

핵심 테제는 단정적이다. LLM 다수결은 분산 합의의 안전성 보장을 상속하지 못한다. PBFT의 n≥3f+1은 “거짓 노드가 최대 f개이고 정직 노드는 독립적”일 때만 성립하는데, LLM에서는 거짓이 서로 상관되어 동시에 다수를 점령할 수 있어 f의 상한 가정이 무너진다. 그러므로 합의 알고리즘은 LLM 충돌해소의 해(解)가 아니라 어휘, 즉 은유로 받아들여야 한다.

3.1 그렇다면 무엇을 빌려오나 — 실무 차용 4선

  1. 정족수 교집합 → 독립 검증자 분리. “다수가 옳다”가 아니라 “독립적으로 산출된 결과가 겹치면 신뢰도가 올라간다”로 읽어라. 단, 진짜 독립이어야 한다. 같은 모델에 같은 프롬프트를 쓴 복제본은 한 표일 뿐이다. 모델과 프롬프트, 도구를 다양화해야 비잔틴 모델의 “독립 정직 노드”에 근접한다(07_07-충돌해소와-합의-안전성-비합성성의 별도 Verifier 권고와 연결된다).
  2. 리더 직렬화 → 단일 권위 슬롯. Raft의 단일 리더처럼, 충돌을 합의로 풀기 전에 순서를 정하는 권위를 07_04-불변규칙-쓰기보호-CLAUDE-AGENTS-Constitutional의 헌법층에 둬라. 합의 비용을 줄이는 가장 싼 방법은 합의를 피하는 것이다(07_03-공유-vs-격리-컨텍스트-트레이드오프 Cognition 처방).
  3. f-내성 산수 → 정족수 크기 설계. 정말 투표로 안전을 사려면 에이전트 3개로는 부족하다. 비잔틴 1명 내성에는 독립 노드 4개 이상과 정족수 3개가 필요하다. 비용 대비 효용을 고객에게 정량적으로 설명하라.
  4. 결정 프로토콜은 작업 유형으로 선택. Kaesberg et al.(2025)에 따르면 추론에는 투표(+13.2%), 지식에는 합의(+2.8%)가 낫다. 투표 전 라운드는 최소화해 다양성을 보존하라.

요약·체크리스트

  • 장애 모델을 구분하라. 크래시(Raft/Paxos, n=2f+1·과반수)는 노드가 거짓말을 안 한다고 가정한다. LLM 오염은 확신에 찬 거짓이므로 비잔틴 모델(PBFT, n≥3f+1·정족수 2f+1)로 사고해야 한다.
  • 정족수 산수. 비잔틴 f명 내성은 노드 3f+1, 정족수 2f+1을 요구한다. 거짓 1명을 견디려면 최소 4노드가 필요하고, “에이전트 3개 다수결”은 비잔틴 1명도 못 막는다.
  • PBFT 3단계(pre-prepare→prepare→commit)의 교훈. 리더가 거짓말을 해도 정족수 합의가 거부한다. 오케스트레이터-워커 검증 분리의 원형이다.
  • LLM 다수결은 합의의 안전성을 상속하지 못한다. 비결정성, 상관된 오류, 동조 압력, 정체성 부재 탓에 “독립 f-내성” 가정이 모두 깨진다. 알고리즘이 아니라 은유로 차용해야 한다.
  • 실측 처방(Kaesberg 2025). 추론은 투표(+13.2%), 지식은 합의(+2.8%)가 낫고, 투표 전 토론 라운드를 늘리면 역효과이며, 다양성을 높이는 것이 핵심이다.
  • 차용 4선. 독립 검증자 분리, 단일 리더 직렬화, 정족수 크기 설계, 작업유형별 프로토콜.
  • 현장 멘트. “에이전트 3개 다수결이면 안전하죠?”라고 물으면, “비잔틴 1명을 견디려면 독립 노드 4개가 필요하고, LLM은 표가 상관돼 그조차 보장되지 않습니다. 다수결은 안전장치가 아니라 보조 신호입니다”라고 답하면 된다.

참고문헌

그래프 뷰

백링크