The Asymmetric Leader Election Algorithm: Another Approach |
| |
Authors: | Guy Louchard Helmut Prodinger |
| |
Affiliation: | (1) Département d’Informatique, Université Libre de Bruxelles, CP 212, Boulevard du Triomphe, B-1050 Bruxelles, Belgium;(2) Helmut Prodinger, Mathematics Department, Stellenbosch University, 7602 Stellenbosch, South Africa |
| |
Abstract: | The asymmetric leader election algorithm has obtained quite a bit of attention lately. In this paper we want to analyze the following asymptotic properties of the number of rounds: Limiting distribution function, all moments in a simple automatic way, asymptotics for p → 0, p → 1 (where p denotes the “killing” probability). This also leads to a few interesting new identities. We use two paradigms: First, in some urn model, we have asymptotic independence of urns behaviour as far as random variables related to urns with a fixed number of balls are concerned. Next, we use a technique easily leading to the asymptotics of the moments of extremevalue related distribution functions. |
| |
Keywords: | leader election Gumbel distribution urn model Mellin transform |
本文献已被 SpringerLink 等数据库收录! |
|