Colliding stacks: A large deviations analysis

DOI10.1002/rsa.3240020404zbMath0737.60097OpenAlexW2145189549WikidataQ62796194 ScholiaQ62796194MaRDI QIDQ3986107

Robert S. Maier

Publication date: 27 June 1992

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/rsa.3240020404

zbMATH Keywords

Markov chainslarge deviationsdynamic data structuresWKB expansionsshared storage allocation

Mathematics Subject Classification ID

Other physical applications of random processes (60K40) Large deviations (60F10) Dynamical aspects of finite-dimensional Hamiltonian and Lagrangian systems (37J99) Data structures (68P05) Applications of queueing theory (congestion, allocation, storage, traffic, etc.) (60K30) Markov processes (60J99)

Related Items

Random walks, heat equation and distributed algorithms ⋮ Large deviations analysis for distributed algorithms in an ergodic Markovian environment ⋮ The exhaustion of shared memory: Stochastic results ⋮ Approximation of excessive backlog probabilities of two tandem queues ⋮ About optimal management of FIFO-queues in two-level memory ⋮ Excessive backlog probabilities of two parallel queues ⋮ Random trees in queueing systems with deadlines ⋮ Optimal management of two parallel stacks in two-level memory ⋮ Hitting time of a corner for a reflected diffusion in the square ⋮ The shape of stretched planar trees ⋮ About optimal management of work-stealing deques in two-level memory ⋮ Analysis of distributed systems via quasi-stationary distributions ⋮ Approximation of the exit probability of a stable Markov modulated constrained random walk

Cites Work

• Unnamed Item
• Unnamed Item
• Path integral evaluation of ALOHA network transients
• Random walks, Gaussian processes and list structures
• Exact formulas for the buddy system
• An Asymptotic Theory of Large Deviations for Markov Jump Processes
• The Metastable Behavior of Infrequently Observed, Weakly Random, One-Dimensional Diffusion Processes
• An Analysis of a Memory Allocation Scheme for Implementing Stacks
• Statistical Properties of the Buddy System
• Large deviations for processes with independent increments