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.
- Tags
-