論文の概要: Nearly-Optimal Consensus Tolerating Adaptive Omissions: Why is a Lot of Randomness Needed?

• arxiv url: http://arxiv.org/abs/2405.04762v2
• Date: Fri, 24 May 2024 04:59:32 GMT
• ステータス: 処理完了
• システム内更新日: 2024-05-27 20:17:43.074466
• Title: Nearly-Optimal Consensus Tolerating Adaptive Omissions: Why is a Lot of Randomness Needed?
• Title（参考訳）: 適応オミッションを許容するほぼ最適合意:なぜ無作為性が必要なのか?
• Authors: Mohammad T. Hajiaghayi, Dariusz R. Kowalski, Jan Olkowski,
• Abstract要約: 同期分散システムにおいて,通信リンクから障害当事者への通信がメッセージの送信を省略できる場合,$n$の自律的パーティによる合意に達するという問題について検討する。 我々は、$O(sqrtnlog2 n)$ラウンドで動作し、$O(n2log3 n)$通信ビットを送信するランダム化アルゴリズムを設計する。 MCアルゴリズムが$O(R)$呼び出しを使用する場合、$Omega(fracn2maxR,nlog n)$ラウンドで動作しないことを示す。
• 参考スコア（独自算出の注目度）: 4.465134753953128
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the problem of reaching agreement in a synchronous distributed system by $n$ autonomous parties, when the communication links from/to faulty parties can omit messages. The faulty parties are selected and controlled by an adaptive, full-information, computationally unbounded adversary. We design a randomized algorithm that works in $O(\sqrt{n}\log^2 n)$ rounds and sends $O(n^2\log^3 n)$ communication bits, where the number of faulty parties is $\Theta(n)$. Our result is simultaneously tight for both these measures within polylogarithmic factors: due to the $\Omega(n^2)$ lower bound on communication by Abraham et al. (PODC'19) and $\Omega(\sqrt{n/\log n})$ lower bound on the number of rounds by Bar-Joseph and Ben-Or (PODC'98). We also quantify how much randomness is necessary and sufficient to reduce time complexity to a certain value, while keeping the communication complexity (nearly) optimal. We prove that no MC algorithm can work in less than $\Omega(\frac{n^2}{\max\{R,n\}\log n})$ rounds if it uses less than $O(R)$ calls to a random source, assuming a constant fraction of faulty parties. This can be contrasted with a long line of work on consensus against an {\em adversary limited to polynomial computation time}, thus unable to break cryptographic primitives, culminating in a work by Ghinea et al. (EUROCRYPT'22), where an optimal $O(r)$-round solution with probability $1-(cr)^{-r}$ is given. Our lower bound strictly separates these two regimes, by excluding such results if the adversary is computationally unbounded. On the upper bound side, we show that for $R\in\tilde{O}(n^{3/2})$ there exists an algorithm solving consensus in $\tilde{O}(\frac{n^2}{R})$ rounds with high probability, where tilde notation hides a polylogarithmic factor. The communication complexity of the algorithm does not depend on the amount of randomness $R$ and stays optimal within polylogarithmic factor.
• Abstract（参考訳）: 同期分散システムにおいて,通信リンクから障害当事者への通信がメッセージの送信を省略できる場合,$n$の自律的パーティによる合意に達するという問題について検討する。 障害当事者は、適応的で完全な情報、計算に縛られない敵によって選択され、制御される。 我々は、$O(\sqrt{n}\log^2 n)$ラウンドで動作するランダム化アルゴリズムを設計し、$O(n^2\log^3 n)$通信ビットを送信する。 したがって、Abraham et al (PODC'19) と $\Omega (\sqrt{n/\log n})$ は Bar-Joseph と Ben-Or (PODC'98) によるラウンド数に対する下界である。 また、通信の複雑さを(ほぼ)最適に保ちながら、時間的複雑さをある値に減らすのに、どの程度のランダム性が必要か、十分な量を定量化します。 我々は、MCアルゴリズムが$O(R)$のランダムソースへの呼び出しを使用する場合、$\Omega(\frac{n^2}{\max\{R,n\}\log n})$のラウンドで動作できないことを証明した。 これは、多項式計算時間に制限された逆数に対するコンセンサスに関する長い研究とは対照的であり、暗号プリミティブを破ることができず、Ghinea et al (EUROCRYPT'22) の論文で、確率1-(cr)^{-r}$の最適$O(r)$ラウンド解が与えられる。 我々の下界は、敵が計算的に非有界である場合、そのような結果を排除することによって、これらの2つの条件を厳密に分離する。 上界側では、$R\in\tilde{O}(n^{3/2})$に対して、高確率での$\tilde{O}(\frac{n^2}{R})$ラウンドにおけるコンセンサスを解くアルゴリズムが存在する。 アルゴリズムの通信複雑性はランダムネスの量R$に依存しず、多対数係数で最適である。

関連論文リスト

• Dueling Optimization with a Monotone Adversary [35.850072415395395]
  凸最適化の一般化である単調逆数を用いたデュエル最適化の問題点について検討する。 目的は、最小値$mathbfx*$の関数$fcolon XをmathbbRdに変換するために、オンラインアルゴリズムを設計することである。
  論文  参考訳（メタデータ） (2023-11-18T23:55:59Z)
• Near-Optimal Quantum Algorithms for Bounded Edit Distance and Lempel-Ziv Factorization [2.684542790908823]
  我々は、$tildeO(sqrtnk+k2)$-timeアルゴリズムを提案し、$tildeO(sqrtnz)$クエリを使用します。 2つ目の貢献は、$tildeO(sqrtnz)$の最適時間複雑性を達成する量子アルゴリズムである。
  論文  参考訳（メタデータ） (2023-11-03T09:09:23Z)
• Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise [50.64137465792738]
  この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。 我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
  論文  参考訳（メタデータ） (2023-07-13T18:59:28Z)
• Asymptotically Optimal Pure Exploration for Infinite-Armed Bandits [4.811176167998627]
  我々は、未知の分布から生じる無限に多くのバンドイットアームを用いて純粋探索を研究する。 私たちのゴールは、平均的な報酬が1-delta$の1つの高品質なアームを、最高の$eta$-fraction of armsの1つとして$varepsilon$内で効率的に選択することにあります。
  論文  参考訳（メタデータ） (2023-06-03T04:00:47Z)
• Near Sample-Optimal Reduction-based Policy Learning for Average Reward MDP [58.13930707612128]
  この研究は、平均報酬マルコフ決定過程(AMDP)における$varepsilon$-Optimal Policyを得る際のサンプルの複雑さを考察する。 我々は、状態-作用対当たりの$widetilde O(H varepsilon-3 ln frac1delta)$サンプルを証明し、$H := sp(h*)$は任意の最適ポリシーのバイアスのスパンであり、$varepsilon$は精度、$delta$は失敗確率である。
  論文  参考訳（メタデータ） (2022-12-01T15:57:58Z)
• On Robust Optimal Transport: Computational Complexity, Low-rank Approximation, and Barycenter Computation [14.80695185915604]
  我々は、最適なトランスポートの2つの頑健なバージョン、$textitRobust Semi-constrained Optimal Transport$ (RSOT) と $textitRobust Unconstrained Optimal Transport$ (ROT) を考える。 離散設定における両方の問題に対して、$widetildemathcalO(fracn2varepsilon)$timeでRSOTとROTの$varepsilon$-approximationsを生成するSinkhornベースのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-02-13T03:55:52Z)
• Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits with Linear Payoff Functions [53.77572276969548]
  我々は、C$2$UCBアルゴリズムが分割マトロイド制約に対して最適な後悔結合$tildeO(dsqrtkT + dk)$を有することを示した。 一般的な制約に対して,C$2$UCBアルゴリズムで腕の報酬推定値を変更するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-20T04:29:18Z)
• 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)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
  S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。 十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
  論文  参考訳（メタデータ） (2020-06-06T13:34:41Z)
• Quantum Distributed Complexity of Set Disjointness on a Line [3.2590610391507444]
  Set Disjointness on a Line は分散コンピューティングシナリオにおける Set Disjointness 問題の変種である。 条件のない$widetildeOmegabig(sqrt[3]n d2+sqrtn, big)$$$$d + 1$プロセッサを持つライン上の集合不整合のラウンドを証明する。
  論文  参考訳（メタデータ） (2020-02-26T21:17:53Z)

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

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