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)}を設計し、任意の2つのノードが信頼できる通信を行えるようにする
制約: ε比率の辺が破壊された場合、最大νn個のノードが「必然的に失敗」するノードになる

重要パラメータ:

疎性: グラフGの次数(理想的には定数)
ラウンド複雑度: 通信ラウンド数(理想的にはO(log n))
計算複雑度: 総計算量(理想的にはpolylog n)
容錯性: (ε,ν)-容錯性。ここでεは定数、ν = ε^Ω(1)

核心技術: バランス置換積

グラフ積の定義: n個の頂点を持つd-正則グラフGとd個の頂点を持つk-正則グラフHが与えられたとき、Z = G ⊙ Hを構成する:

頂点構成: Gの各頂点uをHの1つのコピーCu(クラウドと呼ぶ)で置換
辺関連付け: Gの各辺eとその端点クラウド内の特定の頂点を関連付け
接続規則: Gの辺e = (u,v)に対して、CuとCvの関連付けられた頂点間にdeg(H)本の平行辺を追加

重要な性質:

Zは|V(G)||V(H)|個の頂点を持つ
各頂点の次数は2deg(H)
クラウド内辺数はクラウド間辺数に等しい

プロトコル設計

順列分解:

Z上の順列πをG上のd個の順列π₁,...,πdに分解
各プロトコルR((u,a), π(u,a))は対応するG上のプロトコルR(u,πᵢ(u))をシミュレート

クラウド間プロトコル:

Cv → (v,e₁) → (w,e₂) → Cw

各矢印は多数決投票による伝播プロセスを表す。

シミュレーションプロセス:

初期化: (u,a)はメッセージmをクラウドCu内のすべての頂点に送信
ラウンドシミュレーション: Rの各ラウンドtに対して:
- 各クラウド内の頂点は送信すべきメッセージベクトルを計算
- クラウド間プロトコルを通じてメッセージベクトルを伝送
- 各頂点の履歴記録を更新
結果出力: 目標頂点は多数決投票により最終メッセージを取得