×

Some distributed algorithms revisited. (English) Zbl 0840.90057

Summary: 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 problems related to hitting place and hitting time are solved with tools such as diffusion, random walk techniques and Poisson clumping heuristic.

MSC:

90B05 Inventory, storage, reservoirs
PDFBibTeX XMLCite
Full Text: DOI