On the distribution for the duration of a randomized leader election algorithm
On the distribution for the duration of a randomized leader election algorithm
复制标题
DOI：
10.1214/aoap/1035463332
复制
发表时间：
1996-11
影响因子：
1.8
通讯作者：
J. A. Fill;Hosam M. Mahmoud;W. Szpankowski
中科院分区：
文献类型：
--
作者：
J. A. Fill;Hosam M. Mahmoud;W. Szpankowski
我们调查的持续时间的消除过程中确定一个失败者抛硬币，或者，相当于一个随机的不完全trie的高度。该方法的应用包括计算机网络中领导者的选举。使用直接的概率参数，我们得到的离散分布和高度的时刻的精确表达式。初等近似技术，然后产生渐近的分布。我们表明，不存在极限分布，渐近表达式表现出周期性波动。在许多与数字树相关的类似问题中，没有这样的精确表达式可以导出。因此，我们概述了一个强大的一般方法，梅林变换，Poissonlization和de-Poissonlization的分析技术的基础上，从whh.ich的分布渐近的高度也可以得出。事实上，正是这种复变量方法导致了我们最初对精确分布的发现。复杂;分析方法对于导出均值和方差的渐近表达式是必不可少的，其中还包含小幅度的周期项。
We investigate the duration of an elimination process for identifying a loser by coin tossing, or, equivalently, the height of a random incomplete trie. Applications of the prOcess include the election of a leader in a computer network. Using direct probabilistic arguments we obtain exact expressions for the discrete distribution and the moments of the height. Elementary approximation techniques then yield asymptotics for the distribution. We show that no limiting distribution exists, as the asymptotic expressions exhibit periodic fluctuations. In many similar problems associated with digital trees, no such exact expressions can be derived. We therefore outline a powerful general approach, based on the analytic techniques of Mellin transforms, Poissonlzation, and de-Poissonlzation, from wh.ich distributional asymptotics for the height can also be derived. In fact, it was this complex variables approach that led to our original discovery of the exact distribution. Complex ;:malysis methods are indispensable for deriving asymptotic expressions for the mean and variance, which also contain periodic terms of small magnitude.