Colliding stacks: A large deviations analysis Journal Article uri icon

Overview

abstract

  • AbstractWe analyze the performance of a prototypical scheme for shared storage allocation: two initially empty stacks evolving in a contiguous block of memory of size m. We treat the case in which the stacks are more likely to shrink than grow, but with the probabilities of insertion and deletion allowed to depend arbitrarily on stack height as a fraction of m. New results are obtained on the m → ∞ asymptotics of the stack collision time, and of the final stack heights. The results of Wentzell and Freidlin on the large deviations of Markov chains are used, and the relation of their formalism to the Hamiltonian formulation of classical mechanics is emphasized. Certain results on higher‐order asymptotics follow from WKB expansions.

publication date

  • December 1, 1991

Date in CU Experts

  • March 4, 2026 2:25 AM

Full Author List

  • Maier RS

author count

  • 1

Other Profiles

International Standard Serial Number (ISSN)

  • 1042-9832

Electronic International Standard Serial Number (EISSN)

  • 1098-2418

Additional Document Info

start page

  • 379

end page

  • 420

volume

  • 2

issue

  • 4