論文の概要: Fair Ordering in Replicated Systems via Streaming Social Choice

• arxiv url: http://arxiv.org/abs/2304.02730v4
• Date: Tue, 01 Oct 2024 02:58:56 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-10-02 16:31:20.881599
• Title: Fair Ordering in Replicated Systems via Streaming Social Choice
• Title（参考訳）: ストリーミング社会選択によるレプリケーションシステムの公正な順序付け
• Authors: Geoffrey Ramseyer, Ashish Goel,
• Abstract要約: 先行研究は、複製された状態マシンにおける「かなり」順序付けトランザクションの問題を研究する。 我々は、この問題は社会選択論のレンズを通して最もよく見られていると論じる。
• 参考スコア（独自算出の注目度）: 2.480023305418
• License:
• Abstract: Prior work studies the question of ``fairly'' ordering transactions in a replicated state machine. Each of $n$ replicas receives transactions in a possibly different order, and the system must aggregate the observed orderings into a single order. We argue that this problem is best viewed through the lens of social choice theory, in which (in the preference aggregation problem) rankings on candidates are aggregated into an election result. Two features make this problem novel. First, the number of transactions is unbounded, and an ordering must be defined over a countably infinite set. And second, decisions must be made quickly, with only partial information. Additionally, some faulty replicas might alter their reported observations; their influence on the output should be bounded and well understood. Prior work studies a ``$\gamma$-batch-order-fairness'' property, which divides an ordering into contiguous batches. If a $\gamma$ fraction of replicas receive $\tau$ before $\tau^\prime$, then $\tau^\prime$ cannot be in an earlier batch than $\tau$. We strengthen this definition to require that batches have minimal size ($\gamma$-batch-order-fairness can be vacuously satisfied by large batches) while accounting for the possibility of faulty replicas. This social choice lens enables an ordering protocol with strictly stronger fairness and liveness properties than prior work. We study the Ranked Pairs method. Analysis of how missing information moves through the algorithm allows our streaming version to know when it can output a transaction. Deliberate construction of a tiebreaking rule ensures our algorithm outputs a transaction after a bounded time (in a synchronous network). Prior work relies on a fixed choice of $\gamma$ and bound on the number of faulty replicas $f$, but our algorithm satisfies our definition for every $\frac{1}{2}<\gamma\leq 1$ simultaneously and for any $f$.
• Abstract（参考訳）: 以前の研究は、複製された状態マシンで'`fairly'の順序付けトランザクションの問題を研究していた。 n$のレプリカはそれぞれ、おそらく異なる順序でトランザクションを受け取り、システムは観測された順序を単一の順序に集約しなければならない。 この問題は、(選好集約問題において)候補者のランクが選挙結果に集約される社会選択理論のレンズを通して、最もよく見られていると論じる。 2つの特徴がこの問題を新しくする。 まず、トランザクションの数は非有界であり、順序付けは数え切れない無限集合上で定義されなければならない。 第二に、意思決定は、部分的な情報だけで迅速に行う必要があります。 さらに、いくつかの欠陥のあるレプリカは、報告された観察を変更できるかもしれない。 先行研究は ``$\gamma$-batch-order-fairness'' プロパティを研究し、注文を連続したバッチに分割する。 レプリカの$\gamma$が$\tau$の前に$\tau^\prime$を受け取るなら、$\tau^\prime$は$\tau$よりも早いバッチには入らない。 この定義を強化して、バッチのサイズが最小限であること("\gamma$-batch-order-fairness can be vacuously satisfied by large batchs")と、障害のあるレプリカの可能性を考慮する。 この社会的選択レンズは、前よりも厳密な公正性と生活性を持つ注文プロトコルを可能にする。 ランク付きペア法について検討する。 欠落した情報がアルゴリズムを通してどのように動くかを分析することで、ストリーミングバージョンはいつトランザクションを出力できるかを知ることができる。 整合性ルールの復号化により,アルゴリズムは(同期ネットワーク上で)有界時間後にトランザクションを出力する。 以前の作業では、$\gamma$ の固定された選択と、失敗するレプリカの数に縛られる $f$ に依存していたが、我々のアルゴリズムは、すべての $\frac{1}{2}<\gamma\leq 1$ と任意の $f$ に対して我々の定義を満たす。

関連論文リスト

• Online Linear Programming with Batching [18.989352151219336]
  オンライン線形プログラミング(OLP)をOmegaで研究する。 後悔によって測定されたように、意思決定を遅らせる能力は、より良い運用パフォーマンスをもたらすことが示されます。 提案されたアルゴリズムはすべて、最初のバッチと最後のバッチにのみ到着する顧客の決定を遅らせる。
  論文  参考訳（メタデータ） (2024-08-01T06:13:24Z)
• Federated Combinatorial Multi-Agent Multi-Armed Bandits [79.1700188160944]
  本稿では,Banditを用いたオンライン最適化に適したフェデレーション学習フレームワークを提案する。 この設定では、エージェントのアームサブセットは、個々のアーム情報にアクセスせずにこれらのサブセットに対するノイズの多い報酬を観察し、特定の間隔で協力して情報を共有することができる。
  論文  参考訳（メタデータ） (2024-05-09T17:40:09Z)
• Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
  我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。 SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
  論文  参考訳（メタデータ） (2023-12-13T11:08:25Z)
• Provably Efficient High-Dimensional Bandit Learning with Batched Feedbacks [93.00280593719513]
  本稿では,オンラインインタラクションのT$ステップをバッチに分割したバッチフィードバックによる高次元マルチアームコンテキストバンドレットについて検討する。 具体的には、各バッチは以前のバッチに依存するポリシーに従ってデータを収集し、その報酬はバッチの最後にのみ明らかにする。 我々のアルゴリズムは,$mathcalO( log T)$ バッチで完全に逐次的に設定されたものに匹敵する後悔の限界を達成している。
  論文  参考訳（メタデータ） (2023-11-22T06:06:54Z)
• Concurrent Shuffle Differential Privacy Under Continual Observation [60.127179363119936]
  個人的連続和問題(対数問題)について検討する。 並列シャッフルモデルでは,標準シャッフルモデルに比べて誤差が大幅に改善できることが示されている。
  論文  参考訳（メタデータ） (2023-01-29T20:42:54Z)
• Learning to Order for Inventory Systems with Lost Sales and Uncertain Supplies [21.690446677016247]
  我々は, 在庫管理システムを, 計画的地平線上でのリードタイム$L$とみなし, 供給は不確実であり, 注文量の関数である。 提案アルゴリズムは,O(L+sqrtT)$が$Lgeqlog(T)$である場合に,そのアルゴリズムのコストと,O(L+sqrtT)$に対する最適ポリシーとの相違(英語版)を生じることを示す。
  論文  参考訳（メタデータ） (2022-07-10T22:11:32Z)
• Exponential Separation between Quantum and Classical Ordered Binary Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
  量子順序付き二項決定図($OBDD$)モデルについて検討する。 入力変数の任意の順序で、OBDDの下位境界と上位境界を証明します。 read$k$-times Ordered Binary Decision Diagrams (k$-OBDD$)の幅の階層を拡張します。
  論文  参考訳（メタデータ） (2022-04-22T12:37:56Z)
• A No-Free-Lunch Theorem for MultiTask Learning [19.645741778058227]
  すべてのタスク$P_t$が共通の最適分類器$h*,$を共有する、一見好都合な分類シナリオを考える。 このようなレジームは、$n$と$N$の両方のミニマックスレートを許容するが、適応アルゴリズムは存在しない。
  論文  参考訳（メタデータ） (2020-06-29T03:03:29Z)
• Second-Order Information in Non-Convex Stochastic Optimization: Power and Limitations [54.42518331209581]
  私たちは発見するアルゴリズムを見つけます。 epsilon$-approximate stationary point ($|nabla F(x)|le epsilon$) using $(epsilon,gamma)$surimateランダムランダムポイント。 ここでの私たちの下限は、ノイズのないケースでも新規です。
  論文  参考訳（メタデータ） (2020-06-24T04:41:43Z)
• Optimal $\delta$-Correct Best-Arm Selection for Heavy-Tailed Distributions [2.2940141855172036]
  我々は、$delta$-correctアルゴリズムを用いて、最大平均値を持つものを識別する問題を考察する。 $delta$-correctアルゴリズムの下位境界はよく知られている。 我々は,下界の$delta$-correctアルゴリズムを提案し,$delta$を0に還元する。
  論文  参考訳（メタデータ） (2019-08-24T05:31:49Z)

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

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