Nikki Sonenberg

Mean field models of work stealing in distributed computing

Traditional queueing theory is built upon models that assume each job runs on a single server, but in modern computer systems jobs are parallelizable and can run on multiple servers simultaneously. Work stealing policies can be used to redistribute work across servers to improve response times. We introduce a model of work stealing where (parent) jobs in service spawn new (child) jobs that are initially stored locally but may be subsequently transferred to other servers. Applying a mean field approximation, we use matrix analytic methods to derive the response time distribution for a large-scale system of homogeneous servers with Poisson arrivals and exponential parent and child job durations.

This is joint work with Benny Van Houdt and Grzegorz Kielanski (University of Antwerp).