인과적 브로드캐스트 (Causal Broadcast)는 메시지의 인과관계를 유지하는 브로드 캐스트 프로토콜이다.

요약

• 메시지 전달 시 **인과 관계(causality)**를 유지하는 브로드캐스트 프로토콜
• 메시지 A가 B보다 먼저 발생했다면, 모든 수신자가 A를 B보다 먼저 수신

브로드캐스트 종류 비교

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

인과적 순서란?

Process A: m1 발송 ──────────────→ m3 발송
                    ↘
Process B:           m1 수신 → m2 발송

• m1 → m2 (m2는 m1을 본 후 발송됨)
• m1 → m3 (같은 프로세스에서 m1 후에 m3 발송)
• 따라서: m1, m2가 m3보다 먼저 전달되어야 함

동작 원리

1. 메시지 태깅

• 각 메시지에 벡터 시계 또는 램포트 시계 값 부여

2. 메시지 전달

• 송신자가 메시지 + 태그를 브로드캐스트

3. 수신 및 버퍼링

• 수신자는 도착한 메시지를 버퍼에 저장
• 인과적 선행 메시지가 아직 도착하지 않았으면 대기

4. 조건부 처리

if 모든 인과적 선행 메시지가 처리됨:
    메시지 deliver
else:
    버퍼에서 대기

예시 (벡터 시계 사용)

P1: [1,0,0] m1 전송
P2: m1 수신 후 [1,1,0] m2 전송
P3: m2 먼저 도착 → [1,0,0] 없으므로 버퍼링
    m1 도착 → m1 처리 후 m2 처리

장점

장점	설명
인과적 일관성	원인-결과 관계 유지
데이터 일관성	모든 노드가 일관된 상태 유지
디버깅 용이	이벤트 순서 추적 가능

단점

단점	설명
메시지 오버헤드	벡터 시계 정보 추가 필요
버퍼링 지연	선행 메시지 대기로 인한 지연
메모리 사용	버퍼 관리 필요

참고

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