Some distributed algorithms revisited
Guy Louchard · Stochastic Models · 1995
New results are obtained concerning the analysis of the storage allocation algorithm which permits one to maintain 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 k–dimensional lattice space with several reflecting barriers and one absorbing barrier. Several open problem related to hitting place and hitting time are solved with tools such as diffusion, random walk techniques and Poisson Clumping Heuristic