전체 순서 브로드캐스트 (Total Order Broadcast)

요약

• 모든 노드가 동일한 순서로 메시지를 수신하도록 보장하는 브로드캐스트 프로토콜
• Atomic Broadcast라고도 불림
• 분산 데이터베이스, 복제 시스템에서 핵심적으로 사용

브로드캐스트 종류 비교

종류	신뢰성	순서 보장	설명
Best-effort	❌	❌	전달만 시도
Reliable	✅	❌	모든 노드가 동일 메시지 수신
FIFO	✅	송신자별	같은 송신자 메시지는 순서대로
Causal	✅	인과적	인과 관계 있는 메시지는 순서대로
Total Order	✅	전역	모든 노드가 완전히 동일한 순서로 수신

핵심 속성

1. Agreement (합의)

• 한 노드가 메시지 m을 deliver하면, 모든 정상 노드가 m을 deliver

2. Total Order (전체 순서)

• 노드 A가 m1 → m2 순서로 deliver하면
• 모든 노드가 m1 → m2 순서로 deliver

Node 1: m1 → m2 → m3
Node 2: m1 → m2 → m3  (동일)
Node 3: m1 → m2 → m3  (동일)

구현 방식

1. 단일 리더 (Single Leader)

모든 메시지 → Leader → 순서 결정 → 브로드캐스트

• 간단하지만 Leader가 SPOF(단일 장애점)

2. 합의 알고리즘 (Consensus)

• Paxos, Raft 등 사용
• 모든 노드가 메시지 순서에 대해 합의
• Leader 장애 시에도 동작 가능

3. Lamport 시계 + 타이브레이커

• 램포트 시계 값으로 순서 결정
• 동일 시계 값은 프로세스 ID로 타이브레이크

Total Order vs Consensus

관점	설명
동치 관계	Total Order Broadcast ≡ Consensus
변환	서로 변환 가능
의미	TOB가 있으면 Consensus 구현 가능, 그 역도 성립

장점

장점	설명
강한 일관성	모든 노드가 동일한 상태 유지
예측 가능성	메시지 처리 순서 보장
복제 용이	State Machine Replication 구현 가능

단점

단점	설명
높은 지연	합의 과정으로 인한 latency 증가
복잡성	합의 알고리즘 구현/유지보수 어려움
가용성 트레이드오프	네트워크 파티션 시 가용성 저하 (CAP 정리)

사용 사례

• 분산 데이터베이스 (Spanner, CockroachDB)
• 분산 로그 (Kafka with exactly-once)
• State Machine Replication
• 분산 락

참고

램포트 시계 (Lamport Clock)는 분산시스템에서 이벤트 순서를 결정하기 위한 논리적 시계다. 인과적 브로드캐스트 (Causal Broadcast)는 메시지의 인과관계를 유지하는 브로드 캐스트 프로토콜이다. 비잔틴 장군 문제는 악의적인 노드가 포함됐을 때를 가정한 분산 합의 문제