Kinetically Stable Task Assignment for Networks of Microservers

This paper studies task assignment in a network of resource con-strained computing platforms (called microservers). A task is an abstraction of a computational agent or data that is hosted by the microservers. For example, in an object tracking scenario, a task represents a mobile tracking agent, such as a vehicle location up-date computation, that runs on microservers, which can receive sen-sor data pertaining to the object of interest. Due to object motion, the microservers that can observe a particular object change over time and there is overhead involved in migrating tasks among mi-croservers. Furthermore, communication, processing, or memory constraints, allow a microserver to only serve a limited number of objects at the same time. Our overall goal is to assign tasks to mi-croservers so as to minimize the number of migrations, and thus be kinetically stable, while guaranteeing that as many tasks as possi-ble are monitored at all times. When the task trajectories are known in advance, we show that this problem is NP-complete (even over just two time steps), has an integrality gap of at least 2, and can be solved optimally in polynomial time if we allow tasks to be as-signed fractionally. When only probabilistic information about fu-ture movement of the tasks is known, we propose two algorithms: a multi-commodity flow based algorithm and a maximum match-ing algorithm. We use simulations to compare the performance of these algorithms against the optimum task allocation strategy