arXiv:2411.07302cs.MAcs.CY2024-11

用能力决定抽选概率,提升去中心化系统性能。

Merit-Based Sortition in Decentralized Systems

  • 按参与者能力调整抽中概率,兼顾表现与公平。
  • 实验显示性能提升超随机抽选的2倍以上。
  • 适合需要高效协作的区块链等系统。

在去中心化系统中,常需从全体参与者中选出一个'活跃'子集以满足计算限制或优化资源效率。传统做法是随机抽选,类似古希腊的抽签制度,强调统计代表性。然而,近年来出现的专用去中心化网络需解决具体协调问题,并具备可衡量的成功指标,因此更关注性能优化而非纯粹代表性。本文提出一种'基于绩效的抽签'算法,使每个参与者的入选概率与其质量挂钩,同时通过允许非活跃者无限次尝试,保持经典随机抽签的向上流动特性。通过一系列数值实验,证明该算法使活跃集的表现指标提升超过内在随机性的2倍。这意味着基于绩效的抽签在保证统计显著性能提升的同时,仍维持了经典抽签的公平性与流动性,满足了对性能优化有需求的去中心化系统的关键要求。

原文摘要 · Abstract (English)

In decentralized systems, it is often necessary to select an 'active' subset of participants from the total participant pool, with the goal of satisfying computational limitations or optimizing resource efficiency. This selection can sometimes be made at random, mirroring the sortition practice invented in classical antiquity aimed at achieving a high degree of statistical representativeness. However, the recent emergence of specialized decentralized networks that solve concrete coordination problems and are characterized by measurable success metrics often requires prioritizing performance optimization over representativeness. We introduce a simple algorithm for 'merit-based sortition', in which the quality of each participant influences its probability of being drafted into the active set, while simultaneously retaining representativeness by allowing inactive participants an infinite number of chances to be drafted into the active set with non-zero probability. Using a suite of numerical experiments, we demonstrate that our algorithm boosts the quality metric describing the performance of the active set by $>2$ times the intrinsic stochasticity. This implies that merit-based sortition ensures a statistically significant performance boost to the drafted, 'active' set, while retaining the property of classical, random sortition that it enables upward mobility from a much larger 'inactive' set. This way, merit-based sortition fulfils a key requirement for decentralized systems in need of performance optimization.

去中心化抽签机制性能优化

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。