Kinetically stable task assignment for networks of microservers

ABSTRACT

This paper studies task assignment in a network of resource constrained 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 update computation, that runs on microservers, which can receive sensor 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 microservers. 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 microservers so as to minimize the number of migrations, and thus be kinetically stable, while guaranteeing that as many tasks as possible 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 assigned fractionally. When only probabilistic information about future movement of the tasks is known, we propose two algorithms: a multi-commodity flow based algorithm and a maximum matching algorithm. We use simulations to compare the performance of these algorithms against the optimum task allocation strategy.

REFERENCES

• 1: N. Kong, and A. Schaefer. A Factor 1/2 Approximation Algorithm for Two-Stage Stochastic Matching Problems.
• 2: Subhendu Chattopadhyay , Lisa Higham , Karen Seyffarth, Dynamic and self-stabilizing distributed matching, Proceedings of the twenty-first annual symposium on Principles of distributed computing, July 21-24, 2002, Monterey, California [doi>10.1145/571825.571877]
• 3: Y. Kopidakis, M. Lamari, V. Zissimopoulos. On the Task Assignment Problem: Two New Efficient Heuristic Algorithms. Academic Press 1997.
• 4: Dimitri P. Bertsekas , John N. Tsitsiklis, Parallel and Distributed Computation: Numerical Methods, Athena Scientific, 1997
• 5: Dimitri P. Bertsekas , John N. Tsitsiklis, Some aspects of the parallel and distributed iterative algorithms—a survey, Automatica (Journal of IFAC), v.27 n.1, p.3-21, Jan. 1991 [doi>10.1016/0005-1098(91)90003-K ]
• 6: D.P. Bertsekas. Auction algorithms for network flow problems: A tutorial introduction. Computational Optimization and Applications, 1:766, 1992.
• 7: D.P. Bertsekas, D.A. Castanon, and H. Tsaknakis. "Reverse Auction and the Solution of Inequality Constrained Assignment Problems".
• 8: T. Biedl,C. Duncan, R. Fleischer, S. Kobourov. Tight Bounds on Maximal and Maximum Matchings. Discrete Mathematics, volume 285, number 1--3, August 2004 pp7--15.

INDEX TERMS

Primary Classification:
  A. General Literature
  A.m MISCELLANEOUS

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING

General Terms:
Algorithms

Keywords:
matchings, stochastic processes