論文の概要: Optimal Good-Case Latency for Sleepy Consensus
- arxiv url: http://arxiv.org/abs/2510.06023v1
- Date: Tue, 07 Oct 2025 15:22:29 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-10-08 17:57:08.309318
- Title: Optimal Good-Case Latency for Sleepy Consensus
- Title（参考訳）: 睡眠性コンセンサスのための最適グッドケースレイテンシ
- Authors: Yuval Efron, Joachim Neu, Ling Ren, Ertem Nusret Tas,
- Abstract要約: グッドケース設定は、BBまたはBAプロトコルの可能な最小遅延を、一定の条件下で研究することを目的としている。
ベザンチン放送 (BB) とビザンチン合意 (BA) の双方に対して, 良好なケース遅延の実現可能性と実現不可能性について, フル評価する。
驚くべきことに、不合理なレジリエンスしきい値が現れる: 2ラウンドのグッドケースBBは可能であり、かつ常に、少なくとも活性基の少なくとも$frac1varphi approx 0.618$が正しい場合のみである。
- 参考スコア（独自算出の注目度）: 19.55644245608635
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In the context of Byzantine consensus problems such as Byzantine broadcast (BB) and Byzantine agreement (BA), the good-case setting aims to study the minimal possible latency of a BB or BA protocol under certain favorable conditions, namely the designated leader being correct (for BB), or all parties having the same input value (for BA). We provide a full characterization of the feasibility and impossibility of good-case latency, for both BA and BB, in the synchronous sleepy model. Surprisingly to us, we find irrational resilience thresholds emerging: 2-round good-case BB is possible if and only if at all times, at least $\frac{1}{\varphi} \approx 0.618$ fraction of the active parties are correct, where $\varphi = \frac{1+\sqrt{5}}{2} \approx 1.618$ is the golden ratio; 1-round good-case BA is possible if and only if at least $\frac{1}{\sqrt{2}} \approx 0.707$ fraction of the active parties are correct.
- Abstract（参考訳）: ビザンツ放送(BB)やビザンツ協定(BA)のようなビザンツのコンセンサス問題において、良いケース設定は、特定の条件下でBBまたはBAプロトコルの最小限のレイテンシ、すなわち、指定されたリーダーが正しい(BBの場合)、または同じ入力値を持つすべての当事者(BAの場合)について研究することを目的としている。
同期型スリーピーモデルにおいて,BAとBBの双方に対して,良好な待ち時間の実現可能性と実現不可能性をフルに評価する。
驚いたことに、不合理なレジリエンスしきい値が出現する: 2ラウンドのグッドケースBBが常に可能であれば、少なくとも常に$\frac{1}{\varphi} \approx 0.618$が正しければ、$\varphi = \frac{1+\sqrt{5}}{2} \approx 1.618$が黄金比であり、1ラウンドのグッドケースBAが正しければ、少なくとも$\frac{1}{\sqrt{2}} \approx 0.707$が正である。
関連論文リスト
- Simple Convergence Proof of Adam From a Sign-like Descent Perspective [58.89890024903816]
我々は、Adamが以前の$cal O(fracln TTs14)$よりも$cal O(frac1Ts14)$の最適なレートを達成することを示す。
我々の理論分析は、収束を保証する重要な要因として運動量の役割に関する新たな洞察を提供する。
論文 参考訳（メタデータ） (2025-07-08T13:19:26Z) - Extending Asynchronous Byzantine Agreement with Crusader Agreement [23.27199615640474]
多値BAから二値BAへの新たな削減を提案する。
削減には多値CAを用いるため、$ell$-bit入力のための2つの情報理論CAプロトコルも設計する。
論文 参考訳（メタデータ） (2025-02-04T13:44:41Z) - Resource Allocation under the Latin Square Constraint [3.8028747063484585]
我々は、$n$のラウンドで$n$のエージェント間で$n$の分割不可能なアイテムを割り当てる問題を提起する。
この制約は、各エージェントがラウンド毎に1つ以上のアイテムを受信し、各アイテムを最大1回受信することを保証します。
スケジューリング、リソース管理、実験的設計のような現実世界のアプリケーションは、アロケーションにおける公平性やバランス性を満たすためにラテン四角い制約を必要とする。
論文 参考訳（メタデータ） (2025-01-11T10:53:48Z) - Contextual Combinatorial Bandits with Probabilistically Triggered Arms [55.9237004478033]
確率的に誘発される腕(C$2$MAB-T)を様々な滑らかさ条件下で検討した。
トリガー変調 (TPM) 条件の下では、C$2$-UC-Tアルゴリズムを考案し、後悔すべき$tildeO(dsqrtT)$を導出する。
論文 参考訳（メタデータ） (2023-03-30T02:51:00Z) - Probably Anytime-Safe Stochastic Combinatorial Semi-Bandits [81.60136088841948]
本稿では,時間軸における後悔を最小限に抑えるアルゴリズムを提案する。
提案アルゴリズムは,レコメンデーションシステムや交通機関などの分野に適用可能である。
論文 参考訳（メタデータ） (2023-01-31T03:49:00Z) - Batch-Size Independent Regret Bounds for Combinatorial Semi-Bandits with Probabilistically Triggered Arms or Independent Arms [59.8188496313214]
半帯域 (CMAB) について検討し, 半帯域 (CMAB) におけるバッチサイズ (K$) の依存性の低減に着目した。
まず,確率的に引き起こされるアーム(CMAB-T)を用いたCMABの設定に対して,分散を考慮した信頼区間を持つBCUCB-Tアルゴリズムを提案する。
次に,独立アームを用いた非トリガ型CMABの設定に対して,TPVM条件の非トリガ型を利用したSESCBアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-08-31T13:09:39Z) - Achieving the Pareto Frontier of Regret Minimization and Best Arm
Identification in Multi-Armed Bandits [91.8283876874947]
本稿では,BoBW-lil'UCB$(gamma)$アルゴリズムの設計と解析を行う。
i) RMとBAIの両方の目的に対して最適なアルゴリズムを同時に実行できないことを示す。
また、BoBW-lil'UCB$(gamma)$は、時間複雑性と後悔の点で競合よりも優れていることを示す。
論文 参考訳（メタデータ） (2021-10-16T17:52:32Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。