×

On the distribution for the duration of a randomized leader election algorithm. (English) Zbl 0870.60018

Summary: We investigate the duration of an elimination process for identifying a winner 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, Poissonization and de-Poissonization, from which 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 analysis methods are indispensable for deriving asymptotic expressions for the mean and variance, which also contain periodic terms of small magnitude.

MSC:

60F05 Central limit and other weak theorems
05C05 Trees
05C80 Random graphs (graph-theoretic aspects)
60G70 Extreme value theory; extremal stochastic processes
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abramowitz, M. and Stegun, I., eds. (1972). Handbook of Mathematical Functions. Wiley, New York. · Zbl 0543.33001
[2] Aldous, D. (1989). Probability Approximations via the Poisson Clumping Heuristic. Springer, New York. · Zbl 0679.60013
[3] Anderson, C. (1970). Extreme value theory for a class of discrete distributions with applications to some stochastic processes. J. Appl. Probab. 7 99-113. JSTOR: · Zbl 0192.54202
[4] Arratia, R. and Tavaré, S. (1994). Independent processes approximations for random combinatorial structures. Adv. in Math. 104 90-154. · Zbl 0802.60008
[5] Berndt, B. (1985). Ramanujan’s Notebook, Part I. Springer, New York. · Zbl 0555.10001
[6] Brassard, G. and Bratley, P. (1988). Algorithmics: Theory and Practice. Prentice-Hall, Englewood Cliffs, NJ. · Zbl 0643.68003
[7] D’Aristotile, A., Diaconis, P. and Freedman, D. (1988). On merging of probabilities. Sankhy\?a Ser. A 50 363-380. · Zbl 0698.60005
[8] Devroy e, L. (1986). Non-Uniform Random Variate Generation. Springer, New York. · Zbl 0593.65005
[9] Devroy e, L. (1992). A study of trie-like structures under the density model. Ann. Appl. Probab. 2 402-434. · Zbl 0758.68051
[10] Fill, J. A., Mahmoud, H. M. and Szpankowski, W. (1996). On the distribution for the duration of a randomized leader election algorithm. Technical Report 544, Dept. Math. Sci., Johns Hopkins Univ. · Zbl 0870.60018
[11] Flajolet, P. (1983). On the performance evaluation of extendable hashing and trie search. Acta Inform. 20 345-369. · Zbl 0515.68048
[12] Flajolet, P., Gourdon, X. and Dumas, P. (1995). Mellin transforms and asy mptotics: harmonic sums. Theoret. Comput. Sci. 144 3-58. · Zbl 0869.68057
[13] Flajolet, P. and Martin, G. (1985). Probabilistic counting algorithms for data base applications. J. Comput. Sy stem Sci. 31 182-209. · Zbl 0583.68059
[14] Flajolet, P. and Sedgewick, R. (1995). Mellin transforms and asy mptotics: finite differences and Rice’s integrals. Theoret. Comput. Sci. 144 101-124. · Zbl 0869.68056
[15] Galambos, H. (1987). The Asy mptotic Theory of Extreme Order Statistics. Krieger, Malabar, FL. · Zbl 0634.62044
[16] Gonnet, G. and Munro, J. (1984). The analysis of linear probing sort by the use of a new mathematical transform. J. Algorithms 5 451-470. · Zbl 0606.68058
[17] Grabner, P. (1993). Searching for losers. Random Structures and Algorithms 4 99-110. · Zbl 0788.60020
[18] Holst, L. (1986). On birthday, collector’s, occupancy and other classical urn problems. Internat. Statist. Rev. 54 15-27. JSTOR: · Zbl 0594.60014
[19] Jacquet, P. and Régnier, M. (1986). Trie Partitioning Process: Limiting Distributions. Lecture Notes in Comput. Sci. 214 196-210. Springer, New York. · Zbl 0605.68057
[20] Jacquet, P. and Szpankowski, W. (1989). Ultimate characterizations of the burst response of an interval searching algorithm. SIAM J. Comput. 18 777-791. · Zbl 0679.68052
[21] Jacquet, P. and Szpankowski, W. (1991). Analy sis of tries with Markovian dependency. IEEE Trans. Inform. Theory 37 1470-1475.
[22] Jacquet, P. and Szpankowski, W. (1995). Asy mptotic behavior of the Lempel-Ziv parsing scheme and digital search trees. Theoret. Comput. Sci. 144 161-197. · Zbl 0874.68179
[23] Kac, M. (1949). On the deviations between theoretical and empirical distributions. Proc. Nat. Acad. Sci. U.S.A. 35 252-257. Knuth, D. (1973a). The Art of Computer Programming 1: Fundamentals of Algorithms. AddisonWesley, Reading, MA. Knuth, D. (1973b). The Art of Computer Programming 3: Sorting and Searching. Addison-Wesley, Reading, MA. JSTOR: · Zbl 0033.19303
[24] Kuipers, L. and Niederreiter, H. (1974). Uniform Distribution of Sequences. Wiley, New York. · Zbl 0281.10001
[25] Mahmoud, H. (1992). Evolution of Random Search Trees. Wiley, New York. · Zbl 0762.68033
[26] Mendelson, H. (1982). Analy sis of extendible hashing. IEEE Trans. Software Engrg. SE8 611-619. · Zbl 0491.68096
[27] Pittel, B. (1985). Asy mptotical growth of a class of random trees. Ann. Probab. 13 414-427. · Zbl 0563.60010
[28] Pittel, B. (1986). Paths in a random digital tree: limiting distributions. Adv. in Appl. Probab. 18 139-155. JSTOR: · Zbl 0588.60012
[29] Pittel, B. and Rubin, H. (1992). How many random questions are necessary to identify n distinct objects? J. Combin. Theory Ser. A 55 292-312. · Zbl 0738.05007
[30] Poblete, P. (1987). Approximating functions by their Poisson transform. Inform. Process. Lett. 23 127-130. · Zbl 0654.65012
[31] Prodinger, H. (1993). How to select a loser. Discrete Math. 120 149-159. · Zbl 0795.90103
[32] Rais, B., Jacquet, P. and Szpankowski, W. (1993). Limiting distribution for the depth in PATRICIA tries. SIAM J. Discrete Math. 3 355-362. · Zbl 0798.68067
[33] Régnier, M. and Jacquet, P. (1989). New results on the size of tries. IEEE Trans. Inform. Theory 35 203-205. · Zbl 0684.68038
[34] Rény i, A. (1961). On random subsets of a finite set. Mathematica Cluj 3 355-362. · Zbl 0137.36201
[35] Szpankowski, W. (1987). Solution to a linear recurrence equation arising in the analysis of some algorithms. SIAM J. Algebraic Discrete Methods 8 233-250. · Zbl 0648.68059
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.