Fugu-MT 論文翻訳(概要): Asynchronous Approximate Agreement with Quadratic Communication

論文の概要: Asynchronous Approximate Agreement with Quadratic Communication

arxiv url: http://arxiv.org/abs/2408.05495v3
Date: Sat, 24 May 2025 11:48:26 GMT
ステータス: 翻訳完了
システム内更新日: 2025-05-27 16:58:41.841367
Title: Asynchronous Approximate Agreement with Quadratic Communication
Title（参考訳）: 擬似通信による非同期近似一致
Authors: Mose Mizrahi Erbes, Roger Wattenhofer,
Abstract要約: 非同期ネットワークは$n$のメッセージ送信パーティで、そのうちの最大$t$はビザンチンです。 Abraham, Amit and Dolev [OPODIS '04] はこの問題を最適なレジリエンス $t fracn3$ で $mathbbR$ で解く。これは、信頼できるブロードキャスト毎に$Theta(n2)$メッセージ、またはイテレーション毎に$Theta(n3)$メッセージを取る。
参考スコア（独自算出の注目度）: 23.27199615640474
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We consider an asynchronous network of $n$ message-sending parties, up to $t$ of which are byzantine. We study approximate agreement, where the parties obtain approximately equal outputs in the convex hull of their inputs. In their seminal work, Abraham, Amit and Dolev [OPODIS '04] solve this problem in $\mathbb{R}$ with the optimal resilience $t < \frac{n}{3}$ with a protocol where each party reliably broadcasts a value in every iteration. This takes $\Theta(n^2)$ messages per reliable broadcast, or $\Theta(n^3)$ messages per iteration. In this work, we forgo reliable broadcast to achieve asynchronous approximate agreement against $t < \frac{n}{3}$ faults with quadratic communication. In trees of diameter $D$ and maximum degree $\Delta$, we achieve edge agreement in $\lceil{6\log_2 D}\rceil$ rounds with $\mathcal{O}(n^2)$ messages of size $\mathcal{O}(\log \Delta + \log\log D)$ per round. We do this by designing a 6-round multivalued 2-graded consensus protocol, and by repeatedly using it to reduce edge agreement in a tree of diameter $D$ to edge agreement in a tree of diameter $\frac{D}{2}$. Then, we achieve edge agreement in the infinite path $\mathbb{Z}$, again with the help of 2-graded consensus. Finally, by reducing $\varepsilon$-agreement in $\mathbb{R}$ to edge agreement in $\mathbb{Z}$, we show that our edge agreement protocol enables $\varepsilon$-agreement in $\mathbb{R}$ in $6\log_2(\frac{M}{\varepsilon} + 1) + \mathcal{O}(\log \log \frac{M}{\varepsilon})$ rounds with $\mathcal{O}(n^2 \log \frac{M}{\varepsilon})$ messages and $\mathcal{O}(n^2\log \frac{M}{\varepsilon}\log \log \frac{M}{\varepsilon})$ bits of communication, where $M$ is the maximum input magnitude.
Abstract（参考訳）: 非同期ネットワークは$n$のメッセージ送信パーティで、そのうちの最大$t$はビザンチンです。本研究では,入力の凸内積にほぼ等しい出力が得られるような近似一致について検討する。 Abraham, Amit and Dolev [OPODIS '04] は、最適なレジリエンス $t < \frac{n}{3}$ でこの問題を解く。これは、信頼できるブロードキャスト毎に$\Theta(n^2)$メッセージ、またはイテレーション毎に$\Theta(n^3)$メッセージを取る。本研究では,2次通信を伴う$t < \frac{n}{3}$障害に対して,非同期な近似一致を実現するために,信頼性のある放送を強制する。直径$D$と最大等級$\Delta$の場合、$\lceil{6\log_2 D}\rceil$ rounds with $\mathcal{O}(n^2)$ message of size $\mathcal{O}(\log \Delta + \log\log D)$ per rounds。本研究では,6ラウンドの多値2段階のコンセンサスプロトコルを設計し,直径$D$からエッジコンセンサスへのエッジコンセンサスを,直径$\frac{D}{2}$のツリーのエッジコンセンサスに繰り返し適用する。次に、2階のコンセンサスの助けを借りて、無限経路 $\mathbb{Z}$ におけるエッジコンセンサスを達成する。最後に、$\mathbb{R}$のエッジアグリーメントを$\mathbb{Z}$のエッジアグリーメントに還元することにより、我々のエッジアグリーメントプロトコルは$\mathbb{R}$ in $\mathbb{R}$ in $\log_2(\frac{M}{\varepsilon + 1) + \mathcal{O}(\log \log \frac{M}{\varepsilon})$ rounds with $\mathcal{O}(n^2 \log \frac{M}{\varepsilon})$メッセージと$\mathcal{O}(n^2\log \frac{M}{\varepsilon})$メッセージと$\mathcal{O}(n^2\log \frac{M}{\varepsilon}\log \frac{M}{\varepsilon}$)$ビット通信が可能であることを示す。

関連論文リスト

Log-concave Sampling from a Convex Body with a Barrier: a Robust and Unified Dikin Walk [12.842909157175582]
我々は、$d$-dimensional log-concave distribution $pi(theta) propto exp(-f(theta))$ for $L$-Lipschitz $f$を考える。本稿では,各繰り返しにおける障壁関数のヘシアンに対するスペクトル近似を計算するインプロバストサンプリングフレームワークを提案する。
論文参考訳（メタデータ） (2024-10-08T05:32:51Z)
Near-Optimal Distributed Minimax Optimization under the Second-Order Similarity [22.615156512223763]
本研究では,有限サム構造を目的とする分散楽観的すべり(SVOGS)法を提案する。我々は$mathcal O(delta D2/varepsilon)$、$mathcal O(n+sqrtndelta D2/varepsilon)$、$tildemathcal O(n+sqrtndelta+L)D2/varepsilon)$の局所呼び出しを証明している。
論文参考訳（メタデータ） (2024-05-25T08:34:49Z)
Nearly-Optimal Consensus Tolerating Adaptive Omissions: Why is a Lot of Randomness Needed? [4.465134753953128]
同期分散システムにおいて,通信リンクから障害当事者への通信がメッセージの送信を省略できる場合,$n$の自律的パーティによる合意に達するという問題について検討する。我々は、$O(sqrtnlog2 n)$ラウンドで動作し、$O(n2log3 n)$通信ビットを送信するランダム化アルゴリズムを設計する。 MCアルゴリズムが$O(R)$呼び出しを使用する場合、$Omega(fracn2maxR,nlog n)$ラウンドで動作しないことを示す。
論文参考訳（メタデータ） (2024-05-08T02:17:10Z)
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)
On the Complexity of Finite-Sum Smooth Optimization under the Polyak-{\L}ojasiewicz Condition [14.781921087738967]
本稿では、$min_bf xinmathbb Rd f(bf x)triangleq frac1nsum_i=1n f_i(bf x)$, ここで、$f(cdot)$はパラメータ$mu$と$f_i(cdot)_i=1n$は$L$-mean-squared smoothである。
論文参考訳（メタデータ） (2024-02-04T17:14:53Z)
$\ell_p$-Regression in the Arbitrary Partition Model of Communication [59.89387020011663]
コーディネータモデルにおける分散$ell_p$-regression問題のランダム化通信複雑性について考察する。 p = 2$、すなわち最小二乗回帰の場合、$tildeTheta(sd2 + sd/epsilon)$ bitsの最初の最適境界を与える。 p in (1,2)$ に対して、$tildeO(sd2/epsilon + sd/mathrmpoly(epsilon)$ upper bound を得る。
論文参考訳（メタデータ） (2023-07-11T08:51:53Z)
The Approximate Degree of DNF and CNF Formulas [95.94432031144716]
すべての$delta>0に対して、$はCNFと近似次数$Omega(n1-delta)の式を構築し、基本的には$nの自明な上限に一致する。すべての$delta>0$に対して、これらのモデルは$Omega(n1-delta)$、$Omega(n/4kk2)1-delta$、$Omega(n/4kk2)1-delta$が必要です。
論文参考訳（メタデータ） (2022-09-04T10:01:39Z)
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)
On the Complexity of Minimizing Convex Finite Sums Without Using the Indices of the Individual Functions [62.01594253618911]
有限和の有限ノイズ構造を利用して、大域オラクルモデルの下での一致する$O(n2)$-upper境界を導出する。同様のアプローチを踏襲したSVRGの新規な適応法を提案し、これはオラクルと互換性があり、$tildeO(n2+nsqrtL/mu)log (1/epsilon)$と$O(nsqrtL/epsilon)$, for $mu>0$と$mu=0$の複雑さ境界を実現する。
論文参考訳（メタデータ） (2020-02-09T03:39:46Z)

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

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