ORIE Colloquium on 2/18/2015 - Mariana Olvera-Cravioto: Queues in the Cloud: Generalizing the single server queue to massively parallel networks

Motivated by today’s cloud computing capabilities in large server farms, we present a queueing model where jobs are split into a number of pieces which are then randomly routed to specific servers in the network to be processed in parallel, with the constraint that all fragments of a job must initiate their service at the same time. The main feature of the model is the need for synchronization, which creates blocking and idleness in the network, to be compensated by the fast service time resulting from the parallel processing. The analysis of this model under a many servers limit leads to a natural generalization of Lindley’s equation for the single-server queue, that can be solved within the framework of weighted branching processes. Using the Implicit Renewal Theorem on Trees (Jelenkovic, Olvera-Cravioto (2012)), we describe the exact asymptotics for the limiting waiting time of jobs, which fully extends the celebrated Cramér-Lundberg approximation for the supremum of a random walk to the branching random walk.