×

Random walks, heat equation and distributed algorithms. (English) Zbl 0820.68052

Summary: New results are obtained concerning the analysis of the storage allocation algorithm which permits one to maintain two stacks inside a shared (continuous) memory area of fixed size \(m\) and of the banker’s algorithm (a deadlock avoidance policy). The formulation of these problems is in terms of random walks inside polygonal domains in a two- dimensional lattice space with several reflecting barriers and one absorbing barrier. For the two-stacks problem, the return time to the origin, the time to absorption, the last leaving time from the origin and the number of returns to the origin before absorption are investigated. For the Banker’s algorithm, the trend-free absorbed random walk is analyzed with numerical methods. We finally analyse the average excursion along one axis for the classical random walk: an analytic method enables us to deduce asymptotic results for this average excursion.

MSC:

68W15 Distributed algorithms
65Z05 Applications to the sciences
68N25 Theory of operating systems

Software:

Maple
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Char, B. W.; Geddes, K. O.; Gonnet, G. H.; Monagan, M. B.; Watt, S. M., (MAPLE: Reference Manual (1988), Univ. Waterloo) · Zbl 0758.68038
[2] Descloux, J.; Tolley, M., An accurate algorithm for computing the eigenvalues of polygonal membrane, Comput. Methods Appl. Mech. Engrg., 39, 1, 37-53 (1983) · Zbl 0497.73094
[3] Flajolet, Ph., The evolution of two stacks in bounded space and random walks in a triangle, (Gruska, J.; Rovan, B.; Wiedermann, J., Proc. 12th Symp. on the Mathematical Foundations of Computer Science, 233 (1986), Springer: Springer New York), 325-340, Lecture Notes in Comput. Sci.
[4] Flajolet, Ph.; Odlyzko, A. M., Singularity analysis of generating functions, SIAM J. Discrete Math., 3, 2, 216-240 (1990) · Zbl 0712.05004
[5] Flajolet, Ph.; Salvy, B.; Zimmermann, P., Automatic average-case analysis of algorithms, Theoret. Comput. Sci., 79, 1, 37-109 (1991) · Zbl 0768.68041
[6] Fox, L.; Henrici, P.; Moler, C., Approximations and bounds for eigenvalues of symmetric operators, SIAM J. Numer. Anal., 4, 89-102 (1967) · Zbl 0148.39502
[7] Gakhov, F. D., (Boundary Value Problems (1966), Pergamon: Pergamon Oxford)
[8] Gessel, I. A., A factorization for formal Laurent series and lattice path enumeration, J. Combin. Theory Ser. A, 28, 321-337 (1980)
[9] Goulden, I. P.; Jackson, D. M., Combinatorial Enumeration (1983), Wiley: Wiley New York · Zbl 0519.05001
[10] Greene, D.; Knuth, D. E., Mathematics for the Analysis of Algorithms (1981), Birkhaüser: Birkhaüser Basel
[11] Habermann, A. N., Systems deadlocks, (Chandy, K. M.; Yeh, R. T., Current Trends in Programming Methodology, 3 (1987), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ), 256-297
[12] Knuth, D. E., The Art of Computer Programming: Fundamental Algorithms, I (1969), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0191.17903
[13] Louchard, G.; Schott, R., Random Structures Algorithms, 2, 2, 151-186 (1991) · Zbl 0732.68055
[14] Maier, R. S., Colliding stacks: a large deviations analysis, Random Structures Algorithms, 2, 379-420 (1991) · Zbl 0737.60097
[15] Meir, A.; Moon, J. W., On the altitude of nodes in random trees, Canad. J. Math., 30, 997-1015 (1978) · Zbl 0394.05015
[16] Mushkhelishvili, N. I., Singular Integral Equations (1946), Noordhoff: Noordhoff Groningen
[17] Peterson, J.; Silberschatz, A., Operating Systems Concepts (1983), Addison-Wesley: Addison-Wesley Reading, MA
[18] Tolley, M. D., Grands éléments finis singuliers, Thèse, Service d’Analyse des Contraintes (1972), Univ. Libre Bruxelles · Zbl 0461.65081
[19] Yao, A. C., An analysis of a memory allocation scheme for implementating stacks, SIAM J. Comput., 10, 2, 398-403 (1981) · Zbl 0457.68023
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.