Colliding stacks: A large deviations analysis

Research output: Contribution to journalArticlepeer-review

22 Scopus citations


We 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.

Original languageEnglish (US)
Pages (from-to)379-420
Number of pages42
JournalRandom Structures & Algorithms
Issue number4
StatePublished - 1991


  • Markov chains
  • dynamic data structures
  • large deviations
  • storage allocation

ASJC Scopus subject areas

  • Software
  • General Mathematics
  • Computer Graphics and Computer-Aided Design
  • Applied Mathematics


Dive into the research topics of 'Colliding stacks: A large deviations analysis'. Together they form a unique fingerprint.

Cite this