BIRS Workshop Lecture Videos

Banff International Research Station Logo

BIRS Workshop Lecture Videos

A Skorokhod map on measure valued paths with applications to priority queues Kaspi, Haya


The Skorokhod map on the half-line has proved to be a useful tool for studying processes with non-negativity constraints. In this work we introduce a measure-valued analog of this map that transforms each element ? of a certain class of c`adl`ag paths that take values in the space of signed measures on [0, ?) to a c\'ad\'ag path that takes values in the space of non-negative measures on $[0, \infty)$ in such a way that for each $x>0$, the path $t\to \zeta_t [0, x]$ is transformed via a Skorokhod map on the half-line, and the regulating functions for different $x>0$ are coupled. We establish regularity properties of this map and show that the map provides a convenient tool for studying queueing systems in which tasks are prioritized according to a continuous parameter. One such priority assignment rule is the well known earliest-deadline-first priority rule. We study it both for the single and the many server queueing systems. We show how the map provides a framework within which to form fluid model equations, prove uniqueness of solutions to these equations and establish convergence of scaled state processes to the fluid model. In particular, for these models, we obtain new convergence results in time-inhomogeneous settings, which appear to fall outside the purview of existing approaches and is essential when studying the EDF policy for many servers queues. Based on Joint work with Rami Atar, Anup Biswas and Kavita Ramanan.

Item Media

Item Citations and Data


Attribution-NonCommercial-NoDerivatives 4.0 International