💻 computer science

Hermes: Low Tail-Latency Via Prefix Consensus

Hermes는 뷰(view)가 만료되더라도 진행을 보장하기 위해 임의의 $n-f$ 개 투표로부터 가장 무거운 공통 접두사(heavest common prefix)를 확정하는 프리픽스 합의(prefix consensus)를 활용함으로써, 느리거나 충돌한 리더로 인한 테일 레이턴시 스톨(tail-latency stall)을 제거하는 $n=5f+1$ 프로세스 대상의 2라운드 회전형 리더(rotating-leader) BFT 프로토콜이다.

원저자: Alejandro Ranchal-Pedrosa, Dakai Kang, Neil Giridharan, Dahlia Malkhi, Mohammad Sadoghi, Ben Marsh

게시일 2026-07-29

📖 5 분 읽기🧠 심층 분석

CC BY 4.0

원저자: Alejandro Ranchal-Pedrosa, Dakai Kang, Neil Giridharan, Dahlia Malkhi, Mohammad Sadoghi, Ben Marsh

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

여러 명의 친구가 함께 볼 영화를 결정하려고 합니다. 하지만 이들은 세계 곳 곳에 흩어져 있고, 일부는 인터넷 연결이 불안정하며, 몇몇 장난기 많은 친구들은 가짜 링크를 보내거나 오프라인인 척하며 결정을 방해하려 합니다. 이것이 바로 비잔틴 장애 허용(Byzantine Fault Tolerant, BFT) 합의의 세계입니다. 컴퓨터 과학에서 이는 네트워크의 컴퓨터들이 단 하나의 중앙 통제자 없이도 어떻게 단일한 진실(예: 블록체인에서의 트랜잭션 순서)에 합의하는지를 설명합니다. 목표는 일부 컴퓨터가 고장 나거나 악의적으로 행동하더라도 빠르게 합의에 도달하는 것(낮은 지연 시간)입니다.

수년 동안 이러한 시스템은 다음 단계를 제안하기 위해 "리더"에게 의존해 왔습니다. 리더가 빠르고 정직하다면 모두가 빠르게 합의할 수 있습니다. 하지만 리더가 느리거나 중단되면, 전체 그룹은 타이머가 만료될 때까지 기다렸다가 리더를 포기하고 새로운 리더를 뽑아야 합니다. 여기서 고통스러운 트레이드오프가 발생합니다. 타이머를 길게 설정하면 느린 리더 때문에 영원히 기다려야 하고, 짧게 설정하면 단순히 조금 느린 리더를 버리는 데 시간을 낭비하게 됩니다. 이 "타임아웃 딜레마(timeout dilemma)"는 시스템의 꼬리 부분(tail end)을 느리게 만드는 병목 현상이 됩니다.

이 논문은 이 특정한 골칫거리를 해결하기 위해 설계된 새로운 프로토콜인 **헤르메스(Hermes)**를 소개합니다. 헤르메스는 리더가 느려졌을 때 단순히 포기하는 대신, 리더가 실패하더라도 그룹이 합의할 수 있는 부분까지는 작업을 완료하도록 합니다. 이는 낭비되는 타임아웃을 생산적인 결정으로 바꾸어, 어떤 상황에서도 시스템이 이미 이룬 진전을 잃지 않고 계속 전진할 수 있게 합니다.

문제점: "타임아웃 함정"

릴레이 경주를 상상해 보세요. 팀의 주장(리더)이 다음 주자에게 바톤을 넘겨줘야 합니다. 주장이 빠르면 경주가 순조롭게 진행됩니다. 하지만 주장이 넘어지거나 바톤을 떨어뜨리면, 팀 전체는 심판의 휘슬(타임아웃)이 울릴 때까지 멈춰서 기다려야 하며, 그 후에야 새로운 주장을 뽑고 다시 시작할 수 있습니다.

전통적인 시스템에서 이 휘슬은 도박과 같습니다. 심판이 너무 일찍 휘슬을 불면, 단지 조금 느렸을 뿐이지만 결국 완주했을 수도 있는 주장을 멈추게 될 수 있습니다. 반대로 너무 오래 기다리면, 고장 난 주장이 복구되기를 기다리는 동안 팀은 아무것도 하지 못한 채 시간을 허비하게 됩니다. 두 경우 모두 소비되는 시간은 "죽은 시간(dead time)"입니다. 즉, 진전은 없고 경주는 중단됩니다. 이것이 바로 "테일 레이턴시(tail latency)" 문제입니다. 최악의 시나리오가 전체 시스템을 느리게 만드는 것입니다.

해결책: 헤르메스와 "공통 분모"

헤르메스는 게임의 규칙을 바꿉니다. 느린 리더를 완전한 실패로 취급하는 대신, 헤르메스는 그룹의 부분적인 합의를 하나의 승리로 간주합니다.

작동 방식은 다음과 같은 창의적인 비유로 설명할 수 있습니다. 팀이 블록을 쌓아 긴 탑을 만들려고 한다고 가정해 봅시다.

기존 방식: 리더가 블록을 놓습니다. 모두가 기다립니다. 만약 리더가 멈추면, 팀은 타임아웃을 기다린 후 탑 전체를 버리고 새로운 리더와 함께 처음부터 다시 쌓기 시작합니다.
헤르메스 방식: 리더가 블록을 놓기 시작하지만, 모두가 동시에 자신만의 블록을 놓기 시작합니다. 리더가 빠르면 팀은 리더의 탑을 완벽하게 쌓습니다. 만약 리더가 멈추더라도, 팀은 탑을 버리지 않습니다. 대신, 사람들이 놓은 모든 블록을 살펴보고, 모두가 블록의 순서에 대해 동의하는 가장 긴 구간을 찾아 그 구간을 "완료"된 것으로 선언합니다.

이것이 핵심 혁신인 **접두사 합의(Prefix Consensus)**입니다. 과거에는 두 사람이 약간씩 다른 탑을 위해 투표하면, 그것은 의견 불일치로 간주되어 버려졌습니다. 하지만 헤르메스는 이렇게 말합니다. "잠깐, 이들은 탑의 하단 90%에 대해서는 동의하고 있어! 그 부분은 확정 짓고 다음으로 넘어가자."

헤르메스의 작동 원리: 두 단계의 댄스

헤르메스는 각기 지정된 리더가 있는 "뷰(views, 라운드)" 단위로 작동합니다. 헤르메스는 영리한 두 단계의 댄스를 사용합니다.

1단계 (제안): 모든 구성원은 다음 탑의 모습이 어떠해야 하는지에 대한 자신만의 아이디어를 방송합니다. 리더의 아이디어는 여러 아이디어 중 하나일 뿐입니다.
2단계 (투표):
- 리더가 빠른 경우: 모두가 리더의 제안을 보고 이에 동의하며 투표합니다. 탑은 단 두 번의 메시지 지연(2δ) 만에 리더의 블록만큼 성장합니다.
- 리더가 느리거나 중단된 경우: 타이머가 만료됩니다. 대신, 모두는 라운드를 "취소"하는 것에 투표하는 대신, 자신들이 받은 제안들 중에서 찾을 수 있는 최선의 합의에 투표합니다. 이들은 "가장 무거운 공통 접두사(Heaviest Common Prefix, HCP)"를 찾습니다. 즉, 제안들이 마지막 부분에서 갈라지더라도 모두가 동의하는 가장 긴 블록 시퀀스를 찾는 것입니다.

이는 리더가 실패하더라도 그룹이 뷰(view)를 잃지 않음을 의미합니다. 그들은 탑의 공통 부분을 확정 짓고 즉시 다음 라운드를 시작합니다. 과거에는 막다른 길이었던 "타임아웃" 경로가 이제는 결과를 만들어냅니다.

"접두사(Prefixes)"와 "스킵(Skips)"의 마법

여러 개의 데이터 레인(많은 차선의 교통량과 같은)에서도 이 방식이 작동하게 하기 위해, 헤르메스는 **부모 상대적 델타 팁컷(parent-relative delta tipcuts)**이라는 특별한 인코딩을 사용합니다.

이것은 모든 페이지가 이전 페이지를 참조하는 "당신의 선택에 따라 결말이 바뀌는(Choose Your Own Adventure)" 책과 같습니다. 만약 교통 차선에 자동차(블록) 하나가 빠져 있다면, 헤르메스는 "오류"라고 말하지 않습니다. 대신 그 자리를 명시적으로 "스킵(skipped)"이라고 표시하고 다음 자동차로 넘어갑니다. 이를 통해 시스템은 서로 다른 조각이 빠져 있더라도 서로 다른 제안들을 비교할 수 있습니다. 이는 마치 두 이야기를 비교하는 것과 같습니다. 한 이야기는 한 단락을 건너뛰고 다른 이야기는 포함하고 있더라도, 여전히 시작과 끝 부분은 서로 일치할 수 있으며, 시스템은 그 합의를 확정 짓습니다.

결과: 속도와 안전성

논문은 헤르메스가 안전하며(어떤 정직한 사람들도 확정된 부분에 대해 서로 다르게 동의하지 않음), 활발함(시스템이 항상 계속 움직임)을 수학적으로 증명합니다.

좋은 경우: 리더가 정직하고 빠르면, 헤르메스는 기존의 가장 좋은 시스템들과 마찬가지로 2δ(두 번의 메시지 지연) 만에 확정됩니다.
나쁜 경우: 리더가 느리거나 중단되면, 헤르메스는 2∆ + δ(여기서 ∆는 타임아웃, δ는 네트워크 지연) 만에 공통 합의를 확정합니다. 결정적으로, 이는 뷰 변경(view change)을 위해 기다리는 기존 방식보다 더 빠릅니다. 왜냐하면 뷰를 버리는 데 드는 "낭비된" 시간을 건너뛰기 때문입니다.

저자들은 Erasure Coding(데이터를 조각내어 일부가 손실되어도 재구성할 수 있는 방법)을 사용하여, 많은 수의 데이터 레인을 다룰 때도 헤르메스의 통신 비용을 낮게 유지함을 보여줍니다.

이것이 중요한 이유

헤르메스는 타임아웃 자체를 생산적으로 만듦으로써 "타임아웃 딜레마"를 해결합니다. 실패의 순간을 진전의 순간으로 바꿉니다. "리더가 도착했는가?"를 묻고 기다리는 대신, 헤르메스는 "우리가 무엇에 동의했는가?"를 묻고 앞으로 나아갑니다.

호기심 많은 십 대에게 설명하자면, 이것은 그룹 채팅에서 모두가 계획을 세우려고 노력하는 것과 같습니다. 보통 계획을 제안하던 사람이 답장이 없다면, 기존 방식은 그가 답장할 때까지 기다리거나 새로운 리더와 함께 새로운 채팅방을 만드는 것입니다. 헤르메스는 "알았어, 그 사람이 답장은 없지만, 우리가 보낸 아이디어들을 봐. 우리 모두 첫 세 단계에는 동의했잖아. 그럼 이걸 확정 짓고 네 번째 단계를 계획하자"라고 말하는 것과 같습니다. 이는 누가 실수를 하더라도 그룹이 계속 움직이게 만드는 더 똑똑하고 회복 탄력성 있는 방식입니다.

기술 요약: Hermes: 접두사 합의를 통한 낮은 테일 레이턴시 (Low Tail-Latency)

1. 문제 정의

리더 기반 비잔틴 장애 허용(BFT) 프로토콜은 일반적으로 지정된 리더가 제때 작동할 때만 트랜잭션을 확정(finalize)합니다. 만약 리더가 충돌하거나 느려지면, 뷰(view)를 타임아웃을 통해 종료해야 하며, 이 과정에서 아무런 진전이 없는 "낭비된 뷰(wasted view)"가 발생합니다. 이는 타임아웃 설정에 있어 근본적인 트레이드오프를 생성합니다:

보수적인 타임아웃: 느린 리더를 허용하지만, 모든 충돌한 리더를 긴 정체 상태로 전환합니다.
공격적인 타임아웃: 충돌한 리더를 빠르게 건너뛰지만, 단순히 느린 리더(지리적으로 분산된 시스템에서 흔히 발생하는 현상)의 뷰까지 무효화합니다.

두 경우 모두, 만료된 뷰는 낭비되며 요청은 뷰 변경과 다음 리더의 왕복 시간(round trip)을 기다려야 확정됩니다. 이러한 트레이드오프는 시스템의 "굿 케이스(good case)" 성능보다는 테일 레이턴시(tail latency)를 결정짓는 핵심 요소가 됩니다. 또한, 현대적 아키텍처는 종종 데이터 전파(예: DAG, 레인 기반 설계)와 합의 순서 지정(consensus ordering)을 분리합니다. 이러한 환경에서 제안(proposals)은 스트림의 접두사(prefix)이며, 한 뷰 내의 정직한 제안들은 네트워크 지터(jitter)로 인해 오직 접미사(suffix) 부분에서만 서로 다를 수 있습니다. 기존 프로토콜은 이러한 불일치하는 투표들을 의견 불일치로 간주하여 폐기하며, 그들이 공유하는 공통 접두사를 활용하지 못합니다.

2. 방법론

Hermers는 부분 동기(partial synchrony) 환경 하에서 $n = 5f + 1$ 프로세스를 대상으로 설계된 2라운드 순환 리더(rotating-leader) 프로토콜입니다. 이 프로토콜은 투표가 접두사 관계( $\preceq$ )에 의해 순서가 정해진 값을 운반하고, 쿼럼(quorum)이 동일성(equality)이 아닌 **비교 가능성(comparability)**을 요구하도록 하는 접두사 합의(Prefix Consensus) 메커니즘을 도입합니다.

핵심 메커니즘

2라운드 구조:
1. 1라운드 (제안): 모든 프로세스는 정당화된 제안(justified proposal)을 브로드캐스트합니다. 라운드 로빈 방식의 리더의 제안은 $n$ 개 중 하나입니다.
2. 2라운드 (투표): 모든 프로세스는 단일 투표를 수행합니다.
  - 리더의 제안이 적시에 전달되면, 프로세스들은 그 제안에 투표합니다.
  - 타임아웃( $2\Delta$ )이 경과하고 $n-f$ 개의 유효한 제안이 수신되면, 프로세스들은 가용한 세트에서 선택된 **폴백 제안(fallback proposal)**에 투표합니다.
- 결정적으로, 무효화(nullify) 투표는 존재하지 않습니다.
쿼럼 정의:
- M-노타리제이션(M-notarization): 상호 비교 가능한 $2f+1$ 개의 투표 세트입니다. 이를 통해 다음 뷰로 진행할 수 있습니다.
- L-노타리제이션(L-notarization): $n-f = 4f+1$ 개의 유효한 투표 세트입니다 (반드시 동일할 필요는 없음). 이 세트는 투표들의 **최대 공통 접두사(Heaviest Common Prefix, HCP)**를 확정합니다.
타임아웃 처리:
Hermes는 느린 리더로 인해 뷰가 무효화되는 대신, 타임아웃 경로를 사용하여 $n-f$ 개 투표의 HCP를 확정하는 데 활용합니다. 공격적인 타임아웃은 이제 전체 뷰가 아닌, 투표가 서로 다른 접미사 부분만을 비용으로 치릅니다. HCP는 $2\Delta + \delta$ 에서 확정됩니다.
값 공간 인스턴스화:
프로토콜은 추상적인 접두사 순서 공간 위에서 인스턴스화되며, 두 가지 특정 시나리오에 적용됩니다:
1. 싱글 레인 (최종성 가젯): 동적으로 사용 가능한 체인(예: Ethereum) 위에서 동작합니다. 값은 체인의 팁(tip)이며, 접두사 관계는 조상(ancestry) 관계입니다.
2. 멀티 레인 (Autobahn 스타일): 동시적인 데이터 레인들을 순서화합니다. 이는 다음 사항들에 의해 해결되는 세 가지 특정 과제를 도입합니다:
  - 결정적 인터리빙(Deterministic Interleaving): 레인 위치에 대한 글로벌 순서.
  - 부모 상대적 델타 팁컷(Parent-Relative Delta Tipcut): 이질적인 레인 속도를 처리하기 위해 전체 값을 전송하지 않고 부모 식별자와 명시적 스킵 마커를 사용하는 압축된 표현 방식.
  - 송신자 인덱스 기반 에러 정정 증폭(Sender-Indexed Erasure-Coded Amplification): 통신 복잡도를 $O(n^3 \hat{m})$ 으로 늘리지 않고 가용성을 보장하기 위해, 제안은 에러 정정 코드를 통해 증폭됩니다. 정당화(justifications)는 식별자를 운반하며, 파편(fragments)은 요청 시 재구성됩니다.

3. 주요 기여

Hermes 프로토콜: 무효화 경로가 없는 $n=5f+1$ $n = 5 f + 1$ 의 2라운드 순환 리더 프로토콜입니다.
- 굿 케이스(Good Case): 적시의 정직한 리더 하에서 $2\delta$ 확정.
- 배드 케이스(Bad Case): 임의의 $n-f$ 개 투표의 HCP를 $2\Delta + \delta$ 에서 확정.
- 안전성 및 활성(Safety & Liveness): 추상적인 접두사 값 공간 위에서 증명됨.
싱글 레인 인스턴스화: 값이 체인 팁인 가용 체인을 위한 최종성 가젯.
멀티 레인 인스턴스화: 다음 기능을 갖춘 Autobahn 스타일 레인 설계:
- 결정적 인터리빙.
- 명시적 스킵 인증을 포함한 부모 상대적 델타 팁컷.
- 송신자 인덱스 기반 에러 정정 증폭.
- 복잡도: 뷰당 $O(n^2 \hat{m} + \lambda n^3)$ 비트 및 $O(n^2)$ 메시지 (여기서 $\hat{m}$ 은 레인의 수, $\lambda$ 는 보안 파라미터).
구현 및 평가: 논문에는 구현 및 평가(섹션 8)가 포함되어 있으나, 제공된 텍스트에서 구체적인 수치 결과는 "결과 추가(Add results)"로 표시되어 있습니다.

4. 결과 및 성능

레이턴시:
- 적시의 리더: $2\delta$ 내에 확정됩니다.
- 느리거나 충돌한 리더: $2\Delta + \delta$ 내에 HCP를 확정합니다. 이는 느린 리더가 전체 뷰 변경과 후속 $2\delta$ 라운드를 초래하여, 첫 확정 전까지 총 $2\Delta + 3\delta$ 이상이 걸리는 기존 프로토콜에 비해 유의미한 개선입니다.
통신:
- 증폭을 사용하는 멀티 레인 환경에서, 프로토콜은 전체 값을 전달하는 데 따르는 4차 복잡도( $O(n^3 \hat{m})$ )를 피합니다.
- 굿 케이스에서는 $O(n^2)$ 메시지를 유지합니다. 결함 발생 시, 증폭 트래픽으로 인해 메시지 복잡도가 $O(n^3)$ 으로 증가할 수 있지만, 비트 복잡도는 통제된 상태를 유지합니다.
테일 레이턴시: 타임아웃 경로를 생산적으로 만듦으로써, Hermes는 "낭비된 뷰" 페널티를 제거합니다. 잘못된 뷰에 걸린 요청은 타임아웃과 HCP 확정 비용만 지불할 뿐, 전체 뷰 변경 사이클을 기다릴 필요가 없습니다.

5. 의의

본 논문은 Hermes가 응답성(얼마나 빨리 뷰가 변경되는가)과 안정성(얼마나 많은 뷰 변경이 진전을 만들어내는가) 사이의 트레이드오프를 근본적으로 변화시킨다고 주장합니다.

생산적인 타임아웃: 뷰가 무효화된다는 것을 의미하는 기존 설계와 달리, Hermes는 실패한 리더를 가진 뷰조차도 데이터 스트림의 유용한 접두사를 확정하도록 보장합니다.
현대적 아키텍처와의 호환성: 이는 가용 데이터 전파 계층(DAG 또는 레인 기반 시스템 등)과 합의 사이의 간극을 메워, 이미 전파되었으나 전파 계층에서 약간 갈라졌을 수 있는 블록들을 최종 확정할 수 있게 합니다.
최적성: Hermes는 별도의 복구 프로토콜이나 레이싱 메커니즘을 요구하지 않으면서, 굿 케이스에 대한 이론적 하한선인 $2\delta$ 를 달면서 리더 기반 BFT에서 지속되어 온 테일 레이턴시 문제를 해결합니다.

Hermes는 실패한 리더의 뷰 자체가 스스로를 확정하는 해당 클래스의 유일한 프로토콜로 자리매김하며, 이는 그러한 뷰를 무효화하는 Minimmit이나 접두사 투표를 사용하지만 단일 리더의 제안 내에서만 작동하는 Raptr와 대조됩니다.