FLP로 본 다중 에이전트성: AI 조정의 한계

다중 에이전트 개발은 분산 합의의 문제: FLP와 램포트의 실천

코드 생성을 위한 다중 에이전트 시스템은 분산 시스템에 내재된 근본적인 한계를 안고 있습니다. AI 에이전트 간의 협업은 비동기 네트워크에서 장애가 발생하는 상황에서 합의를 달성하는 것과 동일하며, 이 과정에서 FLP 및 램포트 정리가 엄격한 경계를 설정합니다. 심지어 AGI라도 이러한 불가능성 결과를 회피할 수 없습니다. 명시적 프로토콜과 장애 감지기가 필수적입니다.

에이전트 협업 문제의 공식화

다중 에이전트 개발 과정은 프롬프트 P로 생성되는 유효한 프로그램 집합 Φ(P)를 통해 공식화됩니다. 각 에이전트는 보완된 버전 φ_i를 생성하며, 모든 φ_i가 하나의 φ ∈ Φ(P)를 보완할 때 합의가 성립합니다:

C(φ_1, ..., φ_n) := ∃ φ ∈ Φ(P), ∀i, φ_i refines φ

프로토콜 없이 운영하면 에이전트들은 설계 결정을 두고 경쟁하게 됩니다. 한 에이전트는 콜백 API를 선택하고, 다른 에이전트는 async/await를 선호하면서 Git 충돌이 발생합니다. 리뷰어가 PR을 머지한다고 해서 문제가 해결되는 것은 아닙니다. 오히려 문제를 은폐할 뿐이며, 리베이스 과정에서 작업 손실이 발생할 수 있습니다.

핵심 FLP 조건:

• 비동기 메시지 전달: 에이전트는 도구 호출 후 메시지를 처리할 시점을 스스로 결정합니다.
• 크래시 장애: 프로세스가 종료되거나 루프가 멈추며, pkill 명령으로 통신이 방해될 수 있습니다.

FLP 불가능성 정리: 완벽한 합의는 존재하지 않는다

FLP(Fischer-Lynch-Paterson, 1985)는 비동기 시스템에서 단 하나의 크래시 장애가 발생할 경우, 안전성(정확성), 지속성(해결까지의 진전), 장애 내성 세 가지를 동시에 보장할 수 없다는 것을 증명합니다. 두 가지를 선택하면, 세 번째는 반드시 희생됩니다.

에이전트 환경에서는 무한한 롤백 루프로 나타납니다. 에이전트 A가 설계를 최종화하면, 에이전트 B가 이를 되돌리고, 다시 A가 반응하는 식입니다. 장애 감지기(Chandra-Toueg, 1996) 없이는 지속성이 확보되지 않습니다. 현실적으로 팀은 ps | grep 명령어로 이웃 상태를 점검하며 모델을 부분 동기화 상태로 확장합니다.

잘못된 프롬프트 해석으로 인한 바진타인 장애

람포트(1982): f개의 바진타인 에이전트(프롬프트를 오해하거나 호환되지 않는 φ_i를 생성)가 존재할 경우, 합의를 위해선 n > 3f + 1개의 에이전트가 필요합니다. 바진타인 에이전트는 의사결정을 위조하는 것처럼 행동하며, 마치 전투에서 병사들이 투표를 거짓 보고하는 것과 같습니다.

LLM 투표는 Φ(P)의 광범위한 공간 때문에 비효율적입니다. 해결책은 외부 검증자(테스트, 린터, 검증 도구)를 도입하여 바진타인 장애를 크래시 장애로 전환하고, FLP 모드로 전환하는 것입니다. 이 경우 기존 알고리즘(Paxos 유사)을 활용할 수 있습니다.

검증자의 트레이드오프:

• 지속성을 희생하고 안전성을 높임 (처리 속도 저하).
• 바진타인 위험은 줄이지만, FLP 제약은 여전히 존재.
• n에 따라 확장 가능하며, f < (n-1)/3 조건 충족.

실용적인 파이프라인 설계 원칙

• 장애 감지기는 필수: 에이전트는 이웃의 진행 상황을 모니터링해 정지 상태를 피해야 합니다.
• 작업 분할: 파일 겹침을 최소화하세요 (워크트리 패턴은 CAP의 분할 내성과 유사).
• 타임아웃과 재시작: 제한된 지연 시간을 가진 부분 동기화 구현 (Dwork-Lynch-Stockmeyer, 1988).
• 외부 검증 우선: 테스트 > 협업; 장애를 조기에 변환하세요.
• 임시방편은 피하기: 명시적 합의를 위해 Paxos나 Raft를 사용하세요.

CAP 정리는 적용됩니다. 다중 에이전트 시스템에서는 일관성과 가용성(CA)을 위해 분할 내성을 희생하는 경우가 많습니다.

확장 가능한 시스템을 위한 고급 개념

공통 지식(Halpern-Moses, 1990): "모든 사람이 모두가 안다"는 상태는 프로토콜 없이는 달성 불가능합니다. 이는 공동 문서 실패(예: CLAUDE.md)를 설명합니다.

부분 동기화: 타임아웃이 메시지 복잡성을 증가시키지만, 합의 가능성을 제공합니다.

40년간의 이론적 도구들을 활용하면, AGI의 홍보에 의존하지 않고도 신뢰할 수 있는 파이프라인을 구축할 수 있습니다.

핵심 요약

• 다중 에이전트 시스템은 모델 선택과 무관하게 FLP/CAP 제약 아래에서 분산 합의 문제입니다.
• 검증자(테스트, 린터)는 바진타인 장애를 크래시 장애로 전환해 시스템을 관리 가능하게 만듭니다.
• 장애 감지기와 작업 분할은 최소한의 생산 준비 도구입니다.
• 프롬프트 오해에 대비하려면 n > 3f + 1를 사용하세요.
• AGI는 상수를 개선할 수 있지만, 불가능성의 경계는 바꿀 수 없습니다.

— Editorial Team