European Institute for Statistics, Probability, Stochastic Operations Research
and its Applications

About | Research | Events | People | Reports | Alumni | ContactHome





Sergey Foss (Heriot Watt)

How Big Queues Occur in Multi-Server System with Heavy Tails

We present upper and lower bounds for the tail distribution of the stationary waiting time in the stable $GI/GI/s$ FCFS queue. These bounds depend on the value of the traffic load $\rho$ which is the ratio of mean service and mean interarrival times. For service times with regularly varying tail distribution the bounds are exact up to a constant, and we are able to establish a ``principle of $s-k$ big jumps'' in this case (here $k$ is the integer part of $\rho$). As another corollary of the bounds obtained, we provide a new proof of necessity and sufficiency of conditions for existence of moments of the stationary waiting time.
This is a joint work with Dima Korshunov.

Marc Lelarge (INRIA)

Bipartite graph structures for efficient balancing of heterogeneous loads

Motivated by a problem of contents placement in the context of video-on-demand applications, we compute the size of a maximum spanning subgraph with degree constraints on a random sparse bipartite graph. Our proof makes a rigorous use of the cavity method leading to recursive distributional equations which we solve. We also analyse the structure of the optimal solution by identifying a saturated core. As applications, we characterise the performances of various placement strategies (in function of the memory size available and statistics of the requests).
Joint work with Mathieu Leconte and Laurent Massoulie

Last updated 18-04-11,
by PK