論文の概要: Multivalued Consensus: General Adversaries Require More Communication
- arxiv url: http://arxiv.org/abs/2608.17998v1
- Date: Tue, 18 Aug 2026 16:46:15 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-08-19 21:40:53.409027
- Title: Multivalued Consensus: General Adversaries Require More Communication
- Title（参考訳）: 多値合意:一般の広告主はより多くのコミュニケーションを必要とする
- Abstract要約: 我々は,一般敵(非攻撃者)に対する$n$のフォールトトレラントコンセンサスについて検討する。
無限族 $Z_mathsfprojn,d$ of $Qd$-satisfying $n$-party 逆構造を記述する。
- 参考スコア（独自算出の注目度）: 34.662213518530315
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study $n$-party fault-tolerant consensus against general (non-threshold) adversaries. We describe an infinite family $Z_\mathsf{proj}^{n,d}$ of $Q^d$-satisfying $n$-party adversary structures based on finite projective geometry which cause error-free $R$-round protocols for interactive consistency on $L$-bit inputs to require $Ω(Ln^{2+1/d})$ bits of expected communication. Likewise, $Z_\mathsf{proj}^{n,d}$ causes error-free byzantine agreement and broadcast to cost $Ω(Ln^{1+1/d})$ bits. In every case, the lower bound is $Ω(L_{\mathsf{out}} \cdot n^{1+1/d})$ bits, where $L_{\mathsf{out}}$ is the output length. The family $Z_\mathsf{proj}^{n,d}$ also causes reliable broadcast and byzantine agreement to cost $Ω(Ln^{1+1/d})$ bits of expected communication in asynchronous networks. Moreover, there exists a related family $Z_\mathsf{2\textsf-proj}^{n,d}$ of $Q^d$-satisfying adversary structures that make core set agreement cost $Ω(Ln^{2+1/d})$ bits. These asynchronous lower bounds hold against send-omission adversaries, even if the protocol uses cryptography. Their basis is that if a quorum of non-faulty parties agree on an output and terminate, then the messages they sent before terminating must suffice for the parties outside the quorum to also terminate with the same output. Surprisingly, if we do not require the parties to terminate (stop sending messages) after they output, then these bounds no longer hold. We show this by designing a non-terminating omission-tolerant reliable broadcast protocol that can for any parameter $δ> 1$ be tuned to cost $(1 + \frac{1}{δ- 1})Ln + O(δn^2\log(δn))$ bits, which is of independent interest. Lastly, we show how to get termination with $O(Ln^{1+1/d} + n^2\log n)$ bits (assuming the $Q^d$ condition), and thus prove our asynchronous lower bounds tight.
- Abstract（参考訳）: 我々は,一般敵(非攻撃者)に対する$n$のフォールトトレラントコンセンサスについて検討する。
無限族$Z_\mathsf{proj}^{n,d}$ of $Q^d$-satisfying $n$-party adversary structure based on finite projective geometry that cause error-free $R$-round protocol for interactive consistency on $L$-bit inputs to require $Ω(Ln^{2+1/d})$ bits of expected communication。
同様に、$Z_\mathsf{proj}^{n,d}$はエラーのないビザンチン合意を引き起こし、$Ω(Ln^{1+1/d})$ bitsにブロードキャストする。
いずれの場合も、下界は$Ω(L_{\mathsf{out}} \cdot n^{1+1/d})$ bitsであり、$L_{\mathsf{out}}$は出力長である。
ファミリー$Z_\mathsf{proj}^{n,d}$はまた、信頼できるブロードキャストとビザンチン契約を発生させ、非同期ネットワークにおける期待される通信ビットの$Ω(Ln^{1+1/d})コストを発生させる。
さらに、関連する族 $Z_\mathsf{2\textsf-proj}^{n,d}$ of $Q^d$-satisfying adversary structure that makes core set agreement makes $Ω(Ln^{2+1/d})$ bits が存在する。
これらの非同期な下位境界は、たとえプロトコルが暗号を使っているとしても、送信拒否の敵に対して保持する。
彼らの根拠は、非デフォルトの当事者のクォーラムが出力に同意して終了すると、終了前に送ったメッセージは、クォーラム外の当事者が同じ出力で終了するのに十分である。
意外なことに、出力後、当事者に終了(メッセージの送信を止める)を要求しないのであれば、これらの境界はもはや保持されない。
パラメータ $δ> 1$ が$(1 + \frac{1}{δ-1})Ln + O(δn^2\log(δn))$ bits になるように調整できる。
最後に、$O(Ln^{1+1/d} + n^2\log n)$ bits($Q^d$条件を仮定する)で終端を得る方法を示し、したがって非同期の下位境界を厳密に証明する。
関連論文リスト
- Ordered-Angle Coding for Exact Multiuser Unanimity Testing [0.0]
我々は、シリアル量子アーキテクチャにおいて、$n$変換のみのユーザ間でバイナリユニニミティテストのための順序角符号化を導入する。
加法的代数にはベルの絡み合いは必要ないが、すべての正直な試行において、旅行者は局所的に極大に混合される。
論文 参考訳（メタデータ） (2026-09-04T18:28:01Z) - Sharp Minimax Regret for Infinite-Memory Logistic Prediction [55.29259818039367]
Lag $j$はスケール$r_j$の予測に影響を与え、$n_T,j=T-j+1$の予測ラウンドに入る。
すべての要約可能なエンベロープに対して、局所化された混合は$cR_T(r)leq C_T(r)$を証明する。
指数関数やエンベロープの場合、有限サンプル条件の下では、トープリッツ・デサインの逆は$cR_T(r)geq c_T(r)$である。
論文 参考訳（メタデータ） (2026-08-27T01:31:46Z) - Rényi exponent landscape of multipartite entanglement in free-fermion systems [51.56484100374058]
我々は、Rényi tripartite information $I_3() が小フェルミ運動量での質的に $exclusion-dependent scaling を示すことを示した。
I_m(n)/I_m(1) sim zm-1 to 0$ for all integer $n geq 2$, so the leading von Neumann signal can builded from integer Rényi data。
論文 参考訳（メタデータ） (2026-03-09T22:27:00Z) - Asynchronous Approximate Agreement with Quadratic Communication [35.73648103944158]
非同期ネットワークは$n$のメッセージ送信パーティで、そのうちの最大$t$はビザンチンです。
Abraham, Amit and Dolev [OPODIS '04] はこの問題を最適なレジリエンス $t fracn3$ で $mathbbR$ で解く。
これは、信頼できるブロードキャスト毎に$Theta(n2)$メッセージ、またはイテレーション毎に$Theta(n3)$メッセージを取る。
論文 参考訳（メタデータ） (2024-08-10T09:03:06Z) - 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) - 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) - Breaking The Dimension Dependence in Sparse Distribution Estimation
under Communication Constraints [18.03695167610009]
サンプルサイズ$n$が最低しきい値$n*(s, d, b)$を超えると、$Oleft( fracsn2bright)$の$ell$推定誤差を達成できることを示す。
対話的な設定のために,新しい木に基づく推定手法を提案し,次元自由収束を実現するために必要な最小サンプルサイズを,さらに$n*(s, d, b)$に縮めることを示した。
論文 参考訳（メタデータ） (2021-06-16T07:52:14Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。