An asymptotic study for path reversal

J. Bernabeu-Auban, M. Ahamad, Applying a Path-Compression Technique to Obtain an Efficient Distributed Mutual Exclusion Algorithm, Lecture Notes in Computer Science, vol. 392, Springer, Berlin, 1989, pp. 33–44. Cayley, 1889, A theorem on trees, Quart. J. Math. Oxford Ser., 23, 376 Ginat, 1989, A tight amortized bound for path reversal, Inform. Process. Lett., 31, 3, 10.1016/0020-0190(89)90101-4 Knuth, 1968 C. Lavault, Analysis of an efficient distributed algorithm for mutual exclusion (average-case analysis of path reversal), Lecture Notes in Computer Science, vol. 634, Springer, Berlin, 1992, pp. 133–144. Naimi, 1996, A log(N) distributed mutual exclusion algorithm based on path reversal, J. Parallel Distributed Comput., 34, 1, 10.1006/jpdc.1996.0041 Norris, 1997 Tarjan, 1984, Worst-case analysis of set union algorithms, J. ACM, 31, 245, 10.1145/62.2160 M. Tréhel, P. Gradit, A. Giorgetti, Performances d'un algorithme distribué d'exclusion mutuelle en cas de non-équiprobabilité des requêtes des processus, Réseaux et Systèmes Répartis Calculateurs Parallèles, numéro spécial “Evaluation quantitative des performances des réseaux et systèmes”, vol. 13(6) Hermès Science, Paris, 2001, pp. 557–573. Tréhel, 1987, Un algorithme distribué d'exclusion mutuelle en Log(n), Tech. Sci. Inform., 6, 141 J. van Leeuwen, T. van der Weide, Alternative path compression techniques, Technical Report RUU-CS-77-3, Department of Computer Science, University of Utrecht, Utrecht, The Netherlands, 1977.