<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 12 Issue 4" %>
On Tries, Contention Trees and Their Analysis
Stephan Wagner
Department of Mathematical Sciences, Stellenbosch University, Private Bag X1, Matieland 7602, South Africa
Annals of Combinatorics 12 (4) pp.489-503 December, 2008
AMS Subject Classification: 68W40; 94A40, 68P05
In this paper a survey on tries, a contention resolution algorithm, their similarities, dissimilarities, and their mathematical treatment, will be given. It has already been mentioned in some papers that tries and contention trees follow one common stochastic model, but still they are frequently treated as separate objects in the literature. Hence the aim of the current work is to contribute to the unification of the various results in that area and to exhibit the employed methods, which involve, among others, analytic poissonization/depoissonization and the Mellin transform. For the sake of the example, a new parameter in contention trees, the number of \emph{terminal frames}, will be studied.
Keywords: tries, contention trees, poissonization, Mellin transform


1. N. Abramson, Development of the alohanet, IEEE Trans. Inform. Theory 31 (2) (1985) 119–- 123.

2. J.I. Capetanakis, Tree algorithms for packet broadcast channels, IEEE Trans. Inform. Theory 25 (5) (1979) 505-–515.

3. R. da la Briandais, File searching using variable length keys, In: Proceedings of the Western Joint Computer Conference, Vol. 15, New York, (1959) pp. 295–-298.

4. R. Fagin, J. Nievergelt, N. Pippenger, and H. Raymond Strong, Extendible hashing —a fast access method for dynamic les, ACM Trans. Database Syst. 4 (3) (1979) 315–-344.

5. G. Fayolle, P. Flajolet, and M. Hofri, On a functional equation arising in the analysis of a protocol for a multi-access broadcast channel, Adv. in Appl. Probab. 18 (2) (1986) 441-–472.

6. J.A. Fill, H.M. Mahmoud, and W. Szpankowski, On the distribution for the duration of a randomized leader election algorithm, Ann. Appl. Probab. 6 (4) (1996) 1260-–1283.

v7. P. Flajolet and P. Jacquet, Analytic models for tree communication protocols, In: Flow Control of Congested Networks, Vol. 38, A.R. Odoni, L. Bianco, and G. Szeg¨o, Eds., Springer- Verlag, (1987) pp. 223-–234.

8. P. Flajolet and M. Golin, Mellin transforms and asymptotics: the mergesort recurrence, Acta Inform. 31 (7) (1994) 673–-696.

9. P. Flajolet, X. Gourdon, and P. Dumas, Mellin transforms and asymptotics: harmonic sums, Theoret. Comput. Sci. 144 (1-2) (1995) 3-–58.

10. P. Flajolet, P. Grabner, P. Kirschenhofer, H. Prodinger, and R.F. Tichy, Mellin transforms and asymptotics: digital sums, Theoret. Comput. Sci. 123 (2) (1994) 291-–314.

11. P. Flajolet and R. Sedgewick, Mellin transforms and asymptotics: finite differences and Rice's integrals, Theoret. Comput. Sci. 144 (1-2) (1995) 101–-124.

12. E. Fredkin, Trie memory, Comm. ACM 3 (9) (1960) 490-–499.

13. R.G. Gallagher, Conict resolution in random access broadcast networks, In: Proceedings of the AFOSR Workshop in Communication Theory and Applications, Provincetown, MA, (1978) pp. 74-–76.

14. L. Gy¨or and S. Gyori, Analysis of tree algorithm for collision resolution, In: 2005 International Conference on Analysis of Algorithms, Barcelona, (2005) pp. 357–-364.

15. P. Jacquet and M. R´egnier, Trie partitioning process: limiting distributions, In: Lecture Notes in Comput. Sci. Vol. 214, Springer, Berlin, (1986) pp. 196-–211.

16. P. Jacquet and M. R´egnier, Normal limiting distribution of the size of tries, In: Performance' 87, North-Holland, Amsterdam, (1988) pp. 209-–223.

17. P. Jacquet and W. Szpankowski, Analytical de-Poissonization and its applications, Theoret. Comput. Sci. 201 (1-2) (1998) 1-–62.

18. A.J.E.M. Janssen and M.J.M. de Jong, Analysis of contention tree-algorithms, IEEE Trans. Inform. Theory 46 (6) (2000) 2163-–2172.

19. M.A. Kaplan and E. Gulko, Analytic properties of multiple-access trees, IEEE Trans. Inform. Theory 31 (2) (1985) 255-–263.

20. P. Kirschenhofer, H. Prodinger, and W. Szpankowski, On the variance of the external path length in a symmetric digital trie, Discrete Appl. Math. 25 (1-2) (1989) 129-–143.

21. D.E. Knuth, The Art of Computer Programming, Vol. 3, Addison-Wesley Publishing Co., Reading, Mass., 1973.

22. D. Lazard, On polynomial factorization, In: Proceedings of the European Computer Algebra Conference on Computer Algebra, Lecture Notes in Comput. Sci., Vol. 44, Springer-Verlag, London, (1982) pp. 126–-134.

23. J.L. Massey, Collision resolution algorithms and random access algorithms, In: Multi-User Communication Systems, Springer Verlag, New York, (1981) pp. 73-–137.

24. P. Mathys and P. Flajolet, Q-ary collision resolution algorithms in random-access systems with free or blocked channel access, IEEE Trans. Inform. Theory 31 (2) (1985) 217-–243.

25. G. Park, H.-K. Hwang, P. Nicodeme, and W. Szpankowski, Proles of tries, SIAM J. Comput., to appear.

26. G. Park and W. Szpankowski, Towards a complete characterization of tries, In: Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, ACM, New York, (2005) pp. 33-–42.

27. B. Pittel, Paths in a random digital tree: limiting distributions, Adv. Appl. Probab. 18 (1) (1986) 139-–155.

28. H. Prodinger, How to select a loser, Discrete Math. 120 (1-3) (1993) 149-–159.

29. R. Sedgewick, Algorithms, Addison-Wesley Publishing Co., Advanced Book Program, Reading, MA, 1983.

30. V. Srinivasan and G. Varghese, Fast address lookups using controlled prex expansion, ACM Trans. Comput. Syst. 17 (1) (1999) 1-–40.

31. W. Szpankowski, On a recurrence equation arising in the analysis of conict resolution algorithms, Comm. Statist. Stochastic Models 3 (1) (1987) 89-–114.

32. W. Szpankowski, Some results on V-ary asymmetric tries, J. Algorithms 9 (2) (1988) 224–- 244.

33. B.S. Tsybakov and V.A. Mikha lov, Free synchronous packet access in a broadcast channel with feedback, Problems Inform. Transmission 14 (4) (1978) 32-–59.

34. N.D. Vvedenskaya and B.S. Tsybakov, Packet delay in a multiple-access stack algorithm, Problemy Peredachi Informatsii 20 (2) (1984) 77-–97.