Fugu-MT 論文翻訳(概要): Efficient Extensions for Asynchronous Byzantine Agreement via Weak Agreement

論文の概要: Efficient Extensions for Asynchronous Byzantine Agreement via Weak Agreement

arxiv url: http://arxiv.org/abs/2502.02320v2
Date: Mon, 10 Feb 2025 14:06:17 GMT
ステータス: 翻訳完了
システム内更新日: 2025-02-11 14:28:50.793014
Title: Efficient Extensions for Asynchronous Byzantine Agreement via Weak Agreement
Title（参考訳）: 弱弱協定による非同期ビザンチン協定の効率的な拡張
Authors: Mose Mizrahi Erbes, Roger Wattenhofer,
Abstract要約: 多値BAから二値BAへの新たな還元効果を示す。我々は,多値WAを用いて,$ell$-bit入力のための2つの効率的なWAプロトコルを設計する。我々のWAプロトコルはバイナリBAを、ラウンドオーバーヘッドが一定で、通信オーバーヘッドが$$$2、セキュリティがほぼ最適である複数値BAに拡張します。
参考スコア（独自算出の注目度）: 23.27199615640474
License:
Abstract: In this work, we study multivalued byzantine agreement (BA) in an asynchronous network of $n$ parties where up to $t < \frac{n}{3}$ parties are byzantine. In this setting, we present a novel reduction from multivalued BA to binary BA. This reduction allows one to achieve BA on $\ell$-bit inputs with one instance of binary BA, one instance of weak agreement (WA) on $\ell$-bit inputs and $\Theta(\ell n + n^2)$ bits of additional communication. Afterwards, as our reduction uses multivalued WA, we design two new efficient WA protocols for $\ell$-bit inputs. In the first one, we use almost-universal hashing to achieve statistical security with probability $1 - 2^{-\lambda}$ against $t < \frac{n}{3}$ failures with $\Theta(n^2(\lambda + \log n + \log \ell))$ bits of communication. Then, we replace the hashes with error correcting code symbols and add a step based on the synchronous multivalued BA protocol COOL [DISC '21] to obtain our second protocol, which for any fixed $\varepsilon > 0$ achieves perfect security against $t \leq \frac{n}{3 + \varepsilon}$ failures with $\Theta(\ell n + n^2)$ bits of communication. Used in our reduction, our WA protocols extend binary BA to multivalued BA with a constant round overhead, a quadratic-in-$n$ communication overhead, and near-optimal security.
Abstract（参考訳）: 本研究では,最大$t < \frac{n}{3}$パーティがビザンチンである場合の,$n$パーティの非同期ネットワークにおける多値ビザンチン合意(BA)について検討する。そこで本研究では,多値BAから二値BAへの新たな還元法を提案する。この還元により、$\ell$-bitの入力に対して$\ell$-bitの入力に対してBAを達成することができ、$\ell$-bitの入力に対して弱一致(WA)のインスタンスと$\Theta(\ell n + n^2)の付加的な通信を行う。その後、我々はマルチ値WAを用いて、$$\ell$-bit入力のための2つの効率的なWAプロトコルを設計した。まず、確率1 - 2^{-\lambda}$ $t < \frac{n}{3}$ failures with $\Theta(n^2(\lambda + \log n + \log \ell))$ bits of communication。次に、ハッシュを誤り訂正符号記号に置き換え、同期多重値のBAプロトコルであるCOOL[DISC '21]に基づいてステップを追加し、固定された$\varepsilon > 0$に対して$t \leq \frac{n}{3 + \varepsilon}$障害を$\Theta(\ell n + n^2)$ビットの通信に対して完全なセキュリティを達成する。我々のWAプロトコルは,2値BAを,ラウンドオーバーヘッドが一定であり,通信オーバーヘッドが2-in-$$で,セキュリティがほぼ最適である多値BAに拡張する。

関連論文リスト

Juggernaut: Efficient Crypto-Agnostic Byzantine Agreement [1.77513002450736]
信頼できる設定によって、$tn/2$の汚職が存在する場合、ビザンツ協定の問題を解決することはよく知られている。本稿では, レジリエンスに最適化されたビザンチン合意プロトコルを, 暗号に依存しないものに変換するコンパイラを提案する。以上の結果より,少なくとも$n$の2因子はビット複雑性の最先端性を改善し,早期停止(決定論的)あるいは期待される一定ラウンド複雑性(ランダム化)を提供する。
論文参考訳（メタデータ） (2024-10-15T23:44:29Z)
Asynchronous Approximate Agreement with Quadratic Communication [23.27199615640474]
非同期ネットワークは$n$のメッセージ送信パーティで、そのうちの最大$t$はビザンチンです。本研究では,入力の凸内積にほぼ等しい出力が得られるような近似一致について検討する。これは、信頼できるブロードキャスト毎に$Theta(n2)$メッセージ、またはイテレーション毎に$Theta(n3)$メッセージを取る。
論文参考訳（メタデータ） (2024-08-10T09:03:06Z)
Federated Combinatorial Multi-Agent Multi-Armed Bandits [79.1700188160944]
本稿では,Banditを用いたオンライン最適化に適したフェデレーション学習フレームワークを提案する。この設定では、エージェントのアームサブセットは、個々のアーム情報にアクセスせずにこれらのサブセットに対するノイズの多い報酬を観察し、特定の間隔で協力して情報を共有することができる。
論文参考訳（メタデータ） (2024-05-09T17:40:09Z)
Private Vector Mean Estimation in the Shuffle Model: Optimal Rates Require Many Messages [63.366380571397]
本稿では,プライバシのシャッフルモデルにおけるプライベートベクトル平均推定の問題について検討する。我々は,$tildemathcalOleft(min(nvarepsilon2,d)right)$ message per users を用いて,最適なエラーを実現する新しいマルチメッセージプロトコルを提案する。
論文参考訳（メタデータ） (2024-04-16T00:56:36Z)
Federated Linear Bandits with Finite Adversarial Actions [20.1041278044797]
我々は、M$のクライアントが中央サーバと通信し、線形文脈の帯域幅問題を解決するための連合線形帯域幅モデルについて検討する。逆有限作用集合のユニークな問題に対処するため、FedSupLinUCBアルゴリズムを提案する。我々は、FedSupLinUCBが$tildeO(sqrtd T)$の完全後悔を達成したことを証明している。
論文参考訳（メタデータ） (2023-11-02T03:41:58Z)
Trade-offs between Entanglement and Communication [5.88864611435337]
我々は,$tildeTheta(k5 log3 n)$ qubits of tanglementの量子同時プロトコルが,$O(k)$ qubits of tanglementの2方向ランダム化プロトコルよりも指数関数的に優れていることを示す。私たちの研究以前には、リレーショナルな分離のみが知られていました。
論文参考訳（メタデータ） (2023-06-02T01:49:39Z)
Near-Optimal Regret Bounds for Multi-batch Reinforcement Learning [54.806166861456035]
本研究では,有限水平マルコフ決定過程(MDP)によってモデル化されたエピソディック強化学習(RL)問題をバッチ数に制約を加えて検討する。我々は,$tildeO(sqrtSAH3Kln (1/delta))$tildeO(cdot)をほぼ最適に後悔するアルゴリズムを設計し,$(S,A,H,K)$の対数項を$K$で隠蔽する。技術的貢献は2つある: 1) 探索のためのほぼ最適設計スキーム
論文参考訳（メタデータ） (2022-10-15T09:22:22Z)
SwiftAgg+: Achieving Asymptotically Optimal Communication Load in Secure Aggregation for Federated Learning [83.94234859890402]
SwiftAgg+は、フェデレーション学習システムのための新しいセキュアアグリゲーションプロトコルである。中央サーバは、分散ユーザである$NinmathbbN$のローカルモデルを集約する。
論文参考訳（メタデータ） (2022-03-24T13:12:23Z)
Tight Bounds for the Randomized and Quantum Communication Complexities of Equality with Small Error [1.6522364074260811]
誤差が小さいEquality関数のランダム化および量子化通信複雑性を$epsilon$で調べる。任意の$log(n/epsilon)-log(sqrtn/epsilon)+3$プロトコルが少なくとも$log(n/epsilon)-log(sqrtn/epsilon)-O(1)$ qubitsを通信することを示す。
論文参考訳（メタデータ） (2021-07-25T13:52:42Z)
On Distributed Differential Privacy and Counting Distinct Elements [52.701425652208734]
我々は、$n$ユーザのそれぞれが離散集合から要素を保持する設定について研究する。目標は、すべてのユーザーに対して異なる要素の数を数えることだ。
論文参考訳（メタデータ） (2020-09-21T04:13:34Z)
An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
論文参考訳（メタデータ） (2020-08-24T06:50:57Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。