A0362
Title: Overflow analysis of multiple stacks running on the same memory
Authors: Ali Devin Sezer - Middle East Technical University (Turkey)
Kamil Demirberk Unlu - Ankara University and Middle East Technical University (Turkey) [presenting]
Abstract: A basic mathematical model used for the analysis of dynamic storage allocation is that of a constrained random walk $X$ on the positive orthant ${\mathbb Z}_+^d$ with increments ${\mathcal V} = \{ -e_i, +e_i, i=1,2,3,...,d\}$, where $\{e_i,i=1,2,3,...,d\}$ is the standard basis for ${\mathbb R}^d$, i.e.,$X_{k+1} = X_k + \pi(X_k,Y_k)$ where $\{Y_k\}$ is an i.i.d sequence taking values in ${\mathcal V}$ and $\pi(x,y) = y$ if $x+y \in {\mathbb Z}^d_+$ and $0$ otherwise. This walk models $d$ independent stacks randomly inserting and deleting elements in a jointly used memory of size $n$. Let $\tau_n \doteq \inf \left\{k: \sum_{i=1}^d X_i(k) =n \right\},$ the time when the joint buffer holding these stacks overflows. A much studied quantity in the analysis of this system is ${\mathbb E} \left[ \max_{i=1}^d X_i(\tau_n) \right],$ i.e., the expected size of the longest stack at the time of buffer overflow. The goal is to extend the approximation of the expected size of the longest stack at the time of buffer overflow and the probability that a buffer overflow occurs before the system empties for the constrained random walk representing the stack model. To the best of our knowledge, the current literature on the subject mostly focuses to the case of $d=2$, the goal is to compute approximations also for $d=3$ and, if possible, for $d > 3$.
