Perpetuities in Fair Leader Election Algorithms
Perpetuities in Fair Leader Election Algorithms
复制标题
公平领导者选举算法中的永续性
DOI：
10.1239/aap/1396360110
复制
发表时间：
2013
影响因子：
1.2
通讯作者：
Hosam M. Mahmoud
中科院分区：
文献类型：
--
作者：
Hosam M. Mahmoud
我们考虑一类广泛的公平领导者选举算法，并研究参赛者的持续时间（随机选择的参赛者在比赛中停留的轮数）和算法的总体成本。我们给出了充分的条件，使持续时间具有几何极限分布（由伯努利随机变量构建的永续性），并且使总成本的极限分布（在适当的标准化之后）成为永续性。在此期间，证明是通过一阶 Wasserstein 距离与几何极限的收敛（至 0）来建立的。对于归一化总成本，证明方法也是一阶 Wasserstein 距离的收敛，并通过基于一阶 Wasserstein 度量空间中的收缩映射的参数进行增强，以表明极限接近永续分布方程的唯一定点解。这两个步骤的使用通常称为收缩法。
We consider a broad class of fair leader election algorithms, and study the duration of contestants (the number of rounds a randomly selected contestant stays in the competition) and the overall cost of the algorithm. We give sufficient conditions for the duration to have a geometric limit distribution (a perpetuity built from Bernoulli random variables), and for the limiting distribution of the total cost (after suitable normalization) to be a perpetuity. For the duration, the proof is established via convergence (to 0) of the first-order Wasserstein distance from the geometric limit. For the normalized overall cost, the method of proof is also convergence of the first-order Wasserstein distance, augmented with an argument based on a contraction mapping in the first-order Wasserstein metric space to show that the limit approaches a unique fixed-point solution of a perpetuity distributional equation. The use of these two steps is commonly referred to as the contraction method.