2025-11-14T20:37:10.471640

Constant Degree Networks for Almost-Everywhere Reliable Transmission

Bafna, Minzer

In the almost-everywhere reliable message transmission problem, introduced by [Dwork, Pippenger, Peleg, Upfal'86], the goal is to design a sparse communication network $G$ that supports efficient, fault-tolerant protocols for interactions between all node pairs. By fault-tolerant, we mean that that even if an adversary corrupts a small fraction of vertices in $G$, then all but a small fraction of vertices can still communicate perfectly via the constructed protocols. Being successful to do so allows one to simulate, on a sparse graph, any fault-tolerant distributed computing task and secure multi-party computation protocols built for a complete network, with only minimal overhead in efficiency. Previous works on this problem achieved either constant-degree networks tolerating $o(1)$ faults, constant-degree networks tolerating a constant fraction of faults via inefficient protocols (exponential work complexity), or poly-logarithmic degree networks tolerating a constant fraction of faults. We show a construction of constant-degree networks with efficient protocols (i.e., with polylogarithmic work complexity) that can tolerate a constant fraction of adversarial faults, thus solving the main open problem of Dwork et al.. Our main contribution is a composition technique for communication networks, based on graph products. Our technique combines two networks tolerant to adversarial edge-faults to construct a network with a smaller degree while maintaining efficiency and fault-tolerance. We apply this composition result multiple times, using the polylogarithmic-degree edge-fault tolerant networks constructed in a recent work of [Bafna, Minzer, Vyas'24] (that are based on high-dimensional expanders) with itself, and then with the constant-degree networks (albeit with inefficient protocols) of [Upfal'92].

academic

거의 모든 곳에서 신뢰할 수 있는 전송을 위한 상수 차수 네트워크

기본 정보

논문 ID: 2501.00337
제목: Constant Degree Networks for Almost-Everywhere Reliable Transmission
저자: Mitali Bafna (MIT), Dor Minzer (MIT)
분류: cs.DC (분산 컴퓨팅), cs.CR (암호학), cs.DS (자료구조 및 알고리즘)
발표 시간: 2024년 12월 31일
논문 링크: https://arxiv.org/abs/2501.00337

초록

본 논문은 Dwork 등이 1986년에 제시한 "거의 모든 곳에서 신뢰할 수 있는 메시지 전송" 문제를 연구한다. 목표는 노드 간의 효율적이고 결함 허용적인 프로토콜 상호작용을 지원하는 희소 통신 네트워크 G를 설계하는 것이다. 대적이 G의 일부 정점을 파괴하더라도, 소수의 정점을 제외한 나머지 정점들은 구성된 프로토콜을 통해 완벽하게 통신할 수 있다. 이 문제를 성공적으로 해결하면 희소 그래프에서 완전 네트워크를 위해 구성된 모든 결함 허용적 분산 컴퓨팅 작업 및 보안 다자간 계산 프로토콜을 최소한의 효율성 오버헤드로 시뮬레이션할 수 있다.

이전 연구들은 o(1)개의 결함을 허용하는 상수 차수 네트워크를 구현하거나, 상수 비율의 결함을 허용하는 상수 차수 네트워크를 비효율적인 프로토콜(지수 작업 복잡도)로 구현하거나, 상수 비율의 결함을 허용하는 다중로그 차수 네트워크를 구현했다. 본 논문은 효율적인 프로토콜(다중로그 작업 복잡도)을 갖춘 상수 차수 네트워크 구성을 제시하여 상수 비율의 대적 결함을 허용함으로써 Dwork 등이 제시한 주요 미해결 문제를 해결한다.

연구 배경 및 동기

문제 배경

분산 컴퓨팅의 현실적 필요성: 현대 대규모 네트워크의 계산 작업은 일반적으로 여러 기계 간에 분산 실행되어야 하며, 여기에는 비잔틴 합의, 집단 동전 던지기, 포커 등의 보안 다자간 계산 작업이 포함된다.
완전 연결 가정의 비현실성: 대부분의 결함 허용적 프로토콜은 모든 기계가 다른 모든 기계와 직접 통신할 수 있다고 가정하지만, 이는 현대의 대규모 희소 연결 네트워크에서는 비현실적이다.
희소 네트워크의 도전: 희소 네트워크에서 노드 차수 d가 결함 노드 수 t보다 훨씬 작으면, 일부 정직한 노드는 모든 이웃이 파괴되어 고립될 수 있다.

문제의 중요성

이론적 의의: 분산 컴퓨팅 이론의 기초 문제를 해결하여 이론적 모델과 실제 네트워크 제약을 연결
실용적 가치: 대규모 분산 시스템에 이론적 기초를 제공하며, 특히 블록체인, 분산 저장소 등의 분야에 적용
보안 보장: 대적 환경에서 네트워크 통신 능력을 유지하여 네트워크 보안에 중요한 의미

기존 방법의 한계

DPPU86: 상수 차수 네트워크이지만 ε = 1/log n의 결함률만 허용
Upf92: 상수 차수 네트워크는 상수 비율 결함을 허용하지만 작업 복잡도는 지수급
CGO10, JRV20: 다중로그 차수 네트워크는 상수 비율 결함을 허용하지만 차수는 상수가 아님
BMV24: 다중로그 차수 네트워크, 효율적인 프로토콜이지만 차수는 여전히 상수가 아님

핵심 기여

주요 미해결 문제 해결: 상수 차수, 다중로그 작업 복잡도, 상수 결함 허용률을 동시에 갖춘 최초의 네트워크 구성
조합 기법 제시: 그래프 곱을 기반으로 한 통신 네트워크 조합 기법으로 네트워크 차수를 감소시키면서 효율성과 결함 허용성 유지
이론적 프레임워크 수립: 간선 결함 모델 하에서의 네트워크 조합에 대한 이론적 기초 제공
매개변수 최적화 달성: 모든 핵심 매개변수(차수, 작업 복잡도, 결함 허용률)에서 이상적인 목표 달성

방법 상세 설명

작업 정의

거의 모든 곳에서 신뢰할 수 있는 메시지 전송 문제:

입력: n개 노드의 통신 네트워크 G = (V,E)
목표: 임의의 두 노드가 신뢰할 수 있게 통신할 수 있도록 프로토콜 집합 R = {R(u,v)}을 설계
제약: ε 비율의 간선이 파괴될 때, 최대 νn개의 노드가 "필연적 실패" 노드가 됨

핵심 매개변수:

희소성: 그래프 G의 차수(이상적으로는 상수)
라운드 복잡도: 통신 라운드 수(이상적으로는 O(log n))
작업 복잡도: 총 계산량(이상적으로는 polylog n)
결함 허용성: (ε,ν)-결함 허용, 여기서 ε는 상수, ν = ε^Ω(1)

핵심 기법: 균형 대체 곱

그래프 곱 정의: n개 정점을 가진 d-정규 그래프 G와 d개 정점을 가진 k-정규 그래프 H가 주어졌을 때, Z = G ⊙ H를 구성:

정점 구성: G의 각 정점 u를 H의 사본 C_u로 대체(클라우드라고 함)
간선 관계: G의 각 간선 e를 끝점 클라우드의 특정 정점과 관련시킴
연결 규칙: G의 간선 e = (u,v)에 대해, C_u와 C_v의 관련 정점 사이에 deg(H)개의 평행 간선 추가

핵심 성질:

Z는 |V(G)||V(H)|개의 정점을 가짐
각 정점의 차수는 2deg(H)
클라우드 내 간선 수는 클라우드 간 간선 수와 같음

프로토콜 설계

순열 분해:

Z 위의 순열 π를 G 위의 순열 π₁,...,π_d로 분해
각 프로토콜 R((u,a), π(u,a))는 해당하는 G 위의 프로토콜 R(u,π_i(u))을 시뮬레이션

클라우드 간 프로토콜:

C_v → (v,e₁) → (w,e₂) → C_w

각 화살표는 다수결 투표를 통한 전파 과정을 나타냄.

시뮬레이션 과정:

초기화: (u,a)는 메시지 m을 클라우드 C_u의 모든 정점에 전송
라운드 시뮬레이션: R의 각 라운드 t에 대해:
- 각 클라우드의 정점은 전송할 메시지 벡터 계산
- 클라우드 간 프로토콜을 통해 메시지 벡터 전송
- 각 정점의 이력 기록 업데이트
결과 출력: 목표 정점은 다수결 투표를 통해 최종 메시지 획득