A Multi-agent Systems for Agents Negotiating User-optimal Load-balancing

Résumé

The SMAC team and the dicelab carries out research in the field of Artificial Intelligence. This trainee is concerned with the problem of load balancing and task allocation in distributed systems. In this context, the trainee must provide a multi-agent system which optimize both user-centric and system-centric metrics.

Mots-clés

Multi-agent systems, Distributed system, Negotiation, BigData

Équipe

SMAC/IIC/CRIStAL DICE/RHUL

Encadrants

Anne-Cécile CARON Maxime MORGE Jean-Christophe Routier Kostas Stathis

Présentation détaillée

Requirement

Context

The SMAC team (ULille) and the dicelab (RHUL) carries out research in the field of Artificial Intelligence. While the SMAC team works on the development and the coding of intelligent behaviors for artificial entities, the dicelab design interaction protocol which specify the rules of encounter between individual agents.

Issue

The problem of load balancing and task allocation in distributed systems manifests itself in many applications such as big data processing. This trainee is concerned with a class of such practical applications where (a) some of the resources, e.g. data, required to successfully execute a task are distributed at different network nodes, and (b) some of the nodes may encounter potential execution hazards, e.g. slowing down nodes or communication lags.

In order to tackle the problem of load balancing and task allocation in such applications, multi-agent technologies have received a lot of attention. Most of the existing works adopting the market-based approach [1] model the load-balancing problem as a non-cooperative game in order to optimize user-centric metrics rather than system-centric ones such as the global runtime we consider in [2]. The aim of this trainee is to combine these two approaches.

Work

The work consists of formalizing the multi-agent task allocation problem. By adopting a market-based approach, the load-balancing must be totally decentralized, whereby agents try to minimize the completion time of the last task to perform for each user, i.e. their makespans. We consider as a practical application the distributed deployment of the general-purpose cluster-computing framework Apache Spark [3].

The deliverables are:

  1. The formalization of the problem and the complete specification of the agent behaviour.
  2. The implementation of agent behavior and its integration into a proof-of-concept.
  3. An empirical evaluation of the agent behaviour.

The trainee will take place in the SMAC team (Lille) but a period for an outgoing international mobility in the dicelab at RHUL (UK) is expected.

Bibliography

[1] Yichuan, J. A survey of task allocation and load balancing in distributed systems. IEEE Transactions on Parallel and Distributed Systems,27 (2), pp. 585--599, 2016.

[2] Baert, Q., Caron, A-C., Morge, M., Routier, J-C. & Stathis, K. A Location-Aware Strategy for Agents Negotiating Load-balancing. Proc. of ICTAI, 2019 (To appear).

[3] Zaharia M., Xin R. S., Wendell P., Das T., Armbrust M., Dave A., Meng X., Rosen J., Venkataraman S., Franklin M. J., Ghodsi A., Gonzalez J., Shenker S., Stoica I. Apache Spark: a unified engine for big data processing. Commun. ACM 59(11): 56-65 (2016)