Tail Asymptotics for the Delay in a Brownian Fork-Join Queue

In this paper, we study the tail behavior of ${\max }_{i\le N}{\sup }_{s>0}(W_i(s)+W_A(s)-\beta s)$ as $N\to \mathrm{\infty }$, with $(W_i,i\le N)$ i.i.d. Brownian motions and $W_A$ an independent Brownian motion. This random variable can be seen as the maximum of $N$ mutually dependent Brownian queues, which in turn can be interpreted as the backlog in a Brownian fork-join queue. In previous work, we have shown that this random variable centers around $\frac{{\sigma }^2}{2\beta }\log N$. Here, we analyze the rare-event that this random variable reaches the value $(\frac{{\sigma }^2}{2\beta }+a)\log N$, with $a>0$. It turns out that its probability behaves roughly as a power law with $N$, where the exponent depends on $a$. However, there are three regimes, around a critical point $a^{\star }$; namely, $0<a<a^{\star }$, $a=a^{\star }$, and $a>a^{\star }$. The latter regime exhibits a form of asymptotic independence, while the first regime reveals highly irregular behavior with a clear dependence structure among the $N$ suprema, with a nontrivial transition at $a=a^{\star }$.