Probabilistic analysis of some distributed algorithms

In this paper we analyse: i) a storage allocation algorithm (Knuth [11] Ex.2.2.2.13) which permits to maintain two stacks inside a shared (contiguous) memory area of a fixed size, ii) the well-known banker algorithm which plays a fundamental role in parallel processing (Françon [8], Habermann [10], Peterson, Silberschatz [16]). The natural formulation of the problems to be solved here is in terms of random walks. For (i) the random walk Ym(.) takes place in a triangle in a 2-dimensional lattice space with two reflecting barriers along the axes (a deletion takes no effect on an empty stacks and one absorbing barrier parallel to the second diagonal (the algerithm stops when the combined sizes of the stacks exhaust the available storage). For (ii) the random walk takes place in a rectangle with breaked corner and has four reflecting barriers and one absorbing barrier (see Figure 8). With the help of diffusions techniques, we obtain, asymptotically: - the hitting place (Zm) and time (Tm) distributions on the absorbing boundary - the joined distribution of Zm and Tm- the distribution P[Ym(n)<ym, n