論文の概要: Constant Degree Networks for Almost-Everywhere Reliable Transmission
- arxiv url: http://arxiv.org/abs/2501.00337v1
- Date: Tue, 31 Dec 2024 08:18:28 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-01-05 17:13:23.915461
- Title: Constant Degree Networks for Almost-Everywhere Reliable Transmission
- Title（参考訳）: ほぼすべての場所における信頼伝送のための一定遅延ネットワーク
- Authors: Mitali Bafna, Dor Minzer,
- Abstract要約: 本稿では, 対向断層の一定割合を許容できる, 効率的なプロトコルによる定度ネットワークの構築について述べる。
本研究の主な貢献は,グラフ製品に基づく通信ネットワークの合成技術である。
- 参考スコア（独自算出の注目度）: 0.8210473195536075
- License:
- Abstract: 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].
- Abstract（参考訳）: Dwork, Pippenger, Peleg, Upfal'86] が導入した,ほぼすべての場所で信頼性の高いメッセージ送信問題では,すべてのノード間の通信のために,効率よくフォールトトレラントなプロトコルをサポートする疎結合ネットワークを設計することが目標だ。
フォールトトレラント(英語版)により、敵が少数の頂点を$G$で破壊しても、少数の頂点を除いては、構築されたプロトコルを介して完全に通信することができることを意味する。
成功すれば、スパースグラフ上で、フォールトトレラントな分散コンピューティングタスクをシミュレートし、完全なネットワークのために構築されたセキュアなマルチパーティ計算プロトコルを、効率のオーバーヘッドを最小限に抑えることができる。
この問題に関する以前の研究は、$o(1)$の故障を許容する定度ネットワーク、非効率なプロトコル(特殊作業の複雑さ)を介して一定数の故障を許容する定度ネットワーク、または、一定数の故障を許容する多対数ネットワークを達成した。
効率の良いプロトコル(つまり多対数的作業複雑性)を持つ定数次ネットワークの構築は、対数的欠陥の一定割合を許容し、Dworkらの主なオープンな問題を解くことができる。
本研究の主な貢献は,グラフ製品に基づく通信ネットワークの合成技術である。
本手法は, 敵のエッジフォールトに耐性のある2つのネットワークを組み合わせて, 効率と耐故障性を維持しつつ, より少ないネットワークを構築する。
本稿では,近年の[Bafna, Minzer, Vyas'24](高次元展開器をベースとする)で構築された多対数次エッジフォールトトレラントネットワークを用いて,[Upfal'92]の定数次ネットワーク(非効率なプロトコル)を用いて,この構成結果を複数回適用する。
関連論文リスト
- Decentralized Optimization in Time-Varying Networks with Arbitrary Delays [22.40154714677385]
通信遅延によるネットワークの分散最適化問題を考察する。
そのようなネットワークの例としては、協調機械学習、センサーネットワーク、マルチエージェントシステムなどがある。
通信遅延を模倣するため、ネットワークに仮想非計算ノードを追加し、有向グラフを生成する。
論文 参考訳（メタデータ） (2024-05-29T20:51:38Z) - Communication-Efficient Decentralized Federated Learning via One-Bit
Compressive Sensing [52.402550431781805]
分散連合学習(DFL)は、様々なアプリケーションにまたがる実用性によって人気を博している。
集中型バージョンと比較して、DFLの多数のノード間で共有モデルをトレーニングするのはより難しい。
我々は,iADM (iexact alternating direction method) の枠組みに基づく新しいアルゴリズムを開発した。
論文 参考訳（メタデータ） (2023-08-31T12:22:40Z) - On the Bipartite Entanglement Capacity of Quantum Networks [9.377912974064227]
我々は,非決定論的エンタングルメントスワップ機能を持つデバイスからなる量子ネットワークにおいて,一対のノードに対するマルチパスエンタングルメント分布を考察する。
このフロー問題を解決するために,混合整数2次制約付きプログラム(MIQCP)を提案する。
次に、時間単位当たりのユーザに分散されたEPR状態の最大数として定義される、ネットワーク全体の容量を計算する。
論文 参考訳（メタデータ） (2023-07-10T10:58:02Z) - NodeFormer: A Scalable Graph Structure Learning Transformer for Node
Classification [70.51126383984555]
本稿では,任意のノード間のノード信号を効率的に伝搬する全ペアメッセージパッシング方式を提案する。
効率的な計算は、カーナライズされたGumbel-Softmax演算子によって実現される。
グラフ上のノード分類を含む様々なタスクにおいて,本手法の有望な有効性を示す実験を行った。
論文 参考訳（メタデータ） (2023-06-14T09:21:15Z) - Distributing circuits over heterogeneous, modular quantum computing
network architectures [2.550561768977603]
我々は、ベル状態を介して疎結合な量子コンピューティングモジュールの異種ネットワークを考える。
これらの接続間の操作は計算ボトルネックを構成する。
本稿では,所定の量子回路を,上記型のネットワーク上で実装可能な1つの回路に変換するためのいくつかの手法を紹介する。
論文 参考訳（メタデータ） (2023-05-23T15:14:53Z) - Multiparty Entanglement Routing in Quantum Networks [0.0]
量子ネットワークにおける最大絡み合い状態(GHZn)を抽出するためのプロトコルが提案されている。
このプロトコルは、ネットワークノードのローカル測定とユーザ毎の1キュービットメモリのみを必要とする。
論文 参考訳（メタデータ） (2022-11-12T15:40:34Z) - Acceleration in Distributed Optimization Under Similarity [72.54787082152278]
集中ノードを持たないエージェントネットワーク上での分散(強い凸)最適化問題について検討する。
$varepsilon$-solutionは$tildemathcalrhoObig(sqrtfracbeta/mu (1-)log1/varepsilonbig)$通信ステップ数で達成される。
この速度は、関心のクラスに適用される分散ゴシップ-アルゴリズムの、初めて(ポリログ因子まで)より低い複雑性の通信境界と一致する。
論文 参考訳（メタデータ） (2021-10-24T04:03:00Z) - ADOM: Accelerated Decentralized Optimization Method for Time-Varying
Networks [124.33353902111939]
本稿では,時間変動ネットワーク上の滑らかかつ強凸分散最適化のための高速化手法である adom を提案する。
ネットワーク構造のみに依存する一定の要因まで、その通信は加速されたNesterovメソッドのそれと同じです。
論文 参考訳（メタデータ） (2021-02-18T09:37:20Z) - G-CREWE: Graph CompREssion With Embedding for Network Alignment [18.200401309702173]
本稿では,ネットワークアライメント問題を解決するG-CREWEというフレームワークを提案する。
G-CREWEはノード埋め込みを使用して、ネットワークを2段階の解像度で整列させる。
また,MERGEと呼ばれる新しい圧縮機構を提案し,入力ネットワークのサイズを小さくする。
論文 参考訳（メタデータ） (2020-07-30T05:30:21Z) - Suppress and Balance: A Simple Gated Network for Salient Object
Detection [89.88222217065858]
両問題を同時に解くための単純なゲートネットワーク(GateNet)を提案する。
多レベルゲートユニットの助けを借りて、エンコーダからの貴重なコンテキスト情報をデコーダに最適に送信することができる。
さらに,提案したFold-ASPP操作(Fold-ASPP)に基づくアトラス空間ピラミッドプーリングを用いて,様々なスケールのサリアンオブジェクトを正確に位置決めする。
論文 参考訳（メタデータ） (2020-07-16T02:00:53Z) - Efficient Integer-Arithmetic-Only Convolutional Neural Networks [87.01739569518513]
我々は従来のReLUを境界ReLUに置き換え、その減少は活性化量子化によるものであることを示す。
我々の整数ネットワークは、対応するFPNネットワークと同等の性能を発揮するが、メモリコストは1/4に過ぎず、最新のGPUでは2倍高速である。
論文 参考訳（メタデータ） (2020-06-21T08:23:03Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。