Probabilistic analysis of some distributed algorithms

Abstract

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 Y_m(.) 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 stack) and one absorbing barrier parallel to the second diagonal (the algorithm 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 (Z_m) and time (T_m) distributions on the absorbing boundary

• the joined distribution of Z_m and T_m

• the distribution P[Y_m(n) ≤ y_m, n<T_m)

The two stacks problem has been partially investigated by Yao [17] and more recently by Flajolet [7] with different tools. We provide here an analysis of the general case with new limiting distributions. At our knowledge such kind of analysis has never been done before for the banker algorithm.