論文の概要: Delphi: Efficient Asynchronous Approximate Agreement for Distributed Oracles
- arxiv url: http://arxiv.org/abs/2405.02431v1
- Date: Fri, 3 May 2024 18:57:46 GMT
- ステータス: 処理完了
- システム内更新日: 2024-05-07 20:00:04.544395
- Title: Delphi: Efficient Asynchronous Approximate Agreement for Distributed Oracles
- Title(参考訳): Delphi: 分散Oracleの効率的な非同期近似契約
- Authors: Akhil Bandarupalli, Adithya Bhat, Saurabh Bagchi, Aniket Kate, Chen-Da Liu-Zhang, Michael K. Reiter,
- Abstract要約: 本稿では,$mathcaltildeO(n2)$通信と最小オーバーヘッドを持つ決定論的プロトコルであるDelphiを紹介する。
実験では、Delphiの優れたパフォーマンスが強調され、最先端のプロトコルに比べてレイテンシが大幅に低かった。
- 参考スコア(独自算出の注目度): 18.979637747218394
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Agreement protocols are crucial in various emerging applications, spanning from distributed (blockchains) oracles to fault-tolerant cyber-physical systems. In scenarios where sensor/oracle nodes measure a common source, maintaining output within the convex range of correct inputs, known as convex validity, is imperative. Present asynchronous convex agreement protocols employ either randomization, incurring substantial computation overhead, or approximate agreement techniques, leading to high $\mathcal{\tilde{O}}(n^3)$ communication for an $n$-node system. This paper introduces Delphi, a deterministic protocol with $\mathcal{\tilde{O}}(n^2)$ communication and minimal computation overhead. Delphi assumes that honest inputs are bounded, except with negligible probability, and integrates agreement primitives from literature with a novel weighted averaging technique. Experimental results highlight Delphi's superior performance, showcasing a significantly lower latency compared to state-of-the-art protocols. Specifically, for an $n=160$-node system, Delphi achieves an 8x and 3x improvement in latency within CPS and AWS environments, respectively.
- Abstract(参考訳): コンセンサスプロトコルは、分散(ブロックチェーン)オーラクルからフォールトトレラントなサイバー物理システムまで、様々な新興アプリケーションにおいて不可欠である。
センサ/光子ノードが共通のソースを測定する場合、凸妥当性として知られる正しい入力の凸範囲内で出力を維持することは必須である。
現在の非同期凸合意プロトコルは、ランダム化、実質的な計算オーバーヘッドの増大、あるいは近似した合意手法を用いており、$n$ノードシステムに対する高い$\mathcal{\tilde{O}}(n^3)$通信をもたらす。
本稿では,$\mathcal{\tilde{O}}(n^2)$通信と最小計算オーバーヘッドを持つ決定論的プロトコルであるDelphiを紹介する。
デルフィは、正直な入力は無視可能な確率を除いて有界であると仮定し、文学からの合意原始と、新しい重み付け平均化技術を統合する。
実験結果はDelphiの優れた性能を強調し、最先端のプロトコルに比べてレイテンシが大幅に低いことを示している。
具体的には、$n=160$-nodeシステムの場合、DelphiはCPSとAWS環境でそれぞれ8倍と3倍のレイテンシ改善を実現している。
関連論文リスト
- PIP: Prototypes-Injected Prompt for Federated Class Incremental Learning [17.74913214583399]
Federated Class Incremental Learning (FCIL) は継続学習の新しい方向性である
プロトタイプインジェクトインジェクションプロンプト(PIP)と呼ばれるFCILの新しいリハーサルフリー手法を提案する。
実験結果から,提案手法はCIFAR100, MiniImageNet, TinyImageNetデータセットにおいて, 最大33%の精度向上を実現した。
論文 参考訳(メタデータ) (2024-07-30T10:00:16Z) - Communication-Efficient Adam-Type Algorithms for Distributed Data Mining [93.50424502011626]
我々はスケッチを利用した新しい分散Adam型アルゴリズムのクラス(例:SketchedAMSGrad)を提案する。
我々の新しいアルゴリズムは、反復毎に$O(frac1sqrtnT + frac1(k/d)2 T)$の高速収束率を$O(k log(d))$の通信コストで達成する。
論文 参考訳(メタデータ) (2022-10-14T01:42:05Z) - Matching Pursuit Based Scheduling for Over-the-Air Federated Learning [67.59503935237676]
本稿では,フェデレートラーニング手法を用いて,オーバー・ザ・エアラーニングのための低複雑さデバイススケジューリングアルゴリズムのクラスを開発する。
最先端の提案方式と比較すると,提案方式は極めて低効率なシステムである。
提案手法の有効性は,CIFARデータセットを用いた実験により確認した。
論文 参考訳(メタデータ) (2022-06-14T08:14:14Z) - DASHA: Distributed Nonconvex Optimization with Communication
Compression, Optimal Oracle Complexity, and No Client Synchronization [77.34726150561087]
我々は,分散最適化問題に対する新しい手法であるDASHAを開発し,解析する。
MARINAとは異なり、新しいDASHAとDASHA-MVRは圧縮ベクターのみを送信し、ノードを同期しないため、学習をより実用的なものにしている。
論文 参考訳(メタデータ) (2022-02-02T20:10:40Z) - BEER: Fast $O(1/T)$ Rate for Decentralized Nonconvex Optimization with
Communication Compression [37.20712215269538]
コミュニケーション効率は大規模分散機械学習アプリケーションのボトルネックとして広く認識されている。
本稿では,勾配追跡と通信を併用したBEERを提案し,より高速に収束することを示す。
論文 参考訳(メタデータ) (2022-01-31T16:14:09Z) - Acceleration in Distributed Optimization Under Similarity [72.54787082152278]
集中ノードを持たないエージェントネットワーク上での分散(強い凸)最適化問題について検討する。
$varepsilon$-solutionは$tildemathcalrhoObig(sqrtfracbeta/mu (1-)log1/varepsilonbig)$通信ステップ数で達成される。
この速度は、関心のクラスに適用される分散ゴシップ-アルゴリズムの、初めて(ポリログ因子まで)より低い複雑性の通信境界と一致する。
論文 参考訳(メタデータ) (2021-10-24T04:03:00Z) - Beta-CROWN: Efficient Bound Propagation with Per-neuron Split
Constraints for Complete and Incomplete Neural Network Verification [151.62491805851107]
私たちは、ニューロン毎の分割を完全にエンコードできるバウンド伝搬ベースの検証器である$beta$-crownを開発した。
Beta$-CROWNはLPベースのBaB法よりも3桁近い速さで堅牢性検証が可能です。
BaBを早期に終了することにより、不完全な検証にも使用できます。
論文 参考訳(メタデータ) (2021-03-11T11:56:54Z) - Optimal State Transfer and Entanglement Generation in Power-law
Interacting Systems [0.5592394503914488]
未知の量子ビット状態をマルチキュービットのグリーンバーガー・ホーネ・ザイリンガー状態に符号化するための最適プロトコルを提案する。
このプロトコルは、量子センシング、量子コンピューティング、トポロジカルに順序付けられた状態の準備など、幅広い応用がある。
論文 参考訳(メタデータ) (2020-10-06T18:00:02Z) - Collaborative Learning in the Jungle (Decentralized, Byzantine,
Heterogeneous, Asynchronous and Nonconvex Learning) [8.129477477190363]
我々はByzantineコラボレーティブラーニングを研究し、そこでは$n$ノードが互いのローカルデータから集合的に学習する。
我々は、協調学習が、平均的な合意と呼ばれる新しい形式の合意と等価であることを証明している。
論文 参考訳(メタデータ) (2020-08-03T09:44:07Z) - AQD: Towards Accurate Fully-Quantized Object Detection [94.06347866374927]
本稿では,浮動小数点演算を除去するために,AQDと呼ばれる高精度な量子化オブジェクト検出ソリューションを提案する。
我々のAQDは、非常に低ビットのスキームの下での完全精度と比較して、同等またはそれ以上の性能を実現しています。
論文 参考訳(メタデータ) (2020-07-14T09:07:29Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。