smastaplus

What is SMASTA+ ?

SMASTA+ is a Scala implementation of the Extended Multi-agents Situated Task Allocation.

We study the problem of allocating concurrent jobs composed of situated tasks, underlying the distributed deployment of the MapReduce design pattern on a cluster. In order to minimise the mean flowtime of jobs, we propose a multi-agent strategy that allows the concurrency of negotiation and consumption. Our experiments show that our reallocation strategy, when executed continuously during the consumption process improves the flowtime.

In this video, we compare the consumption of 4 jobs with 8 nodes composed of 56 tasks with 10 resources per tasks replicated 3 times without negotiation (at left) and with negotiation (at right). The realised flowtime of the initial random allocation is 0.646 mn. The simulated flowtime of the reallocation is 0.440 mn. The realised flowtime of the reallocation is 0.510 mn. The rate of performance improvement is 21 %

We have implemented our prototype with the Scala programming language and the Akka toolkit. The latter, which is based on the actor model, allows us to fill the gap between the specification and its implementation.

Requirements

In order to run SMASTA+ you need:

• the Java virtual machine JVM 17.0.2

• the Java Constraint Programming Library (JaCoP) for comparison (included)

• eventually the python library pyDCOP for Distributed Constraints Optimization for comparison

• eventually IBM ILOG CPLEX Optimization Studio 12.8 for comparison

• eventually PlantUML for drawing the sequence diagram of the negotiation

• eventually Node.js for monitoring reallocation during consumption

In order to compile the code you need:

• the programming language Scala 2.13.8

• the interactive build tool SBT 1.6.2

Dependencies

SMASTA+ is built upon:

• some Scala libraries, i.e Scala Java-Time, ScalaTest and uPickle

• some data visualisation Javascript libraries, i.e. D3 and Vega Lite Grammar

Run

java -jar smastaplus-assembly-X.Y.jar org.smastaplus.utils.MASTAPlusConsumer

Usage:

Usage: java -jar smastaplus-assembly-X.Y.jar org.smastaplus.utils.MASTAPlusConsumer -v -m
The following options are available:
-v: verbose (false by default)
-m: monitor disabled (true by default)

or

java -jar smastaplus-assembly-X.Y.jar org.smastaplus.utils.MASTAPlusBalancer -g -d -v examples/stap/ex1.txt ex1AllocationFound.txt

Usage:

Usage: java -jar smastaplus-assembly-X.Y.jar org.smastaplus.utils.MASTAPlusBalancer [-vwfghidslcomh] inputFilename outputFilename
The following options are available:
-v: verbose (false by default)
-t: trace for interaction protocol (false by default)
-w: monitor (false by default)
-f: LocalFlowtime (Makespan by default)
-g: GlobalFlowtime (Makespan by default)
-i: LocalFlowtimeAndMakespan (Makespan by default)
-j: LocalFlowtimeAndGlobalFlowtime (Makespan by default)
-d: distributed (false by default)
-s: swap (false by default)
-n: multi-delegation without swap (false by default)
-l: linear programming (false by default)
-c: constraint programming (false by default) with a 15 seconds timeout
-o: dcop-like approach (false by default) with the specific heuristic
-m: MGM2 (false by default) with a 15 seconds timeout
-h: heuristic approach (false by default)

You can draw the sequence diagram of the negotiation process in the following way:

java -jar plantuml.jar -tsvg ./log.txt

Installation

Copy the file src/main/resources/application.conf.example to src/main/resources/application.conf and set up in this file the path toward to the installation folder of SMASTA+

smastaplus = "/path/to/smastaplus/"

Compile

sbt compile

then

sbt "run org.smastaplus.utils.MASTAPlusConsumer -v -m

or

sbt "run org.smastaplus.utils.MASTAPlusBalancer -v -d -g examples/stap/ex1.txt ex1AllocationFound.txt"

eventually

sbt assembly

Monitoring

The instructions for monitoring the task allocation are here.

Specifications

The technical specification of the framework is here.

Empirical evaluation

For reproducibility, the empirical evaluation of SMASTA+ can be performed with the following instructions.

Publications

Ellie Beauprez, Anne-Cécile Caron, Maxime Morge, Jean-Christophe Routier. Consommation adaptative par négociation continue. Trente-et-unièmes journées francophones sur les systèmes multi-agents (JFSMA), Jun 2023, Strasbourg, France. pp. 21-30.

Ellie Beauprez, Anne-Cécile Caron, Maxime Morge, Jean-Christophe Routier. Délégation de lots de tâches pour la réduction de la durée moyenne de réalisation. Revue Ouverte d’Intelligence Artificielle. Volume 4, no 2, 2023, 193-221.

Ellie Beauprez, Anne-Cécile Caron, Maxime Morge, Jean-Christophe Routier. Échange de tâches pour la réduction de la durée moyenne de réalisation. Trentièmes journées francophones sur les systèmes multi-agents (JFSMA), Jun 2022, Saint-Étienne, France. pp. 19-28.

Ellie Beauprez, Anne-Cécile Caron, Maxime Morge, Jean-Christophe Routier. Task Bundle Delegation for Reducing the Flowtime. In A. P. ROCHA, L. STEELS & H. J. van den HERIK (Éd.), Agents and Artificial Intelligence, 13th International Conference, ICAART 2021, Online streaming, February 4-6, 2021, Revised Selected Papers (p. 22-45). Springer. https://doi.org/10.1007/978-3-031-10161-8_2

Ellie Beauprez, Anne-Cécile Caron, Maxime Morge, Jean-Christophe Routier. Une stratégie de négociation multi-agents pour réduire la durée moyenne de réalisation. Vingt-neuvièmes journées francophones sur les systèmes multi-agents (JFSMA), Jun 2021, Bordeaux, France. pp.31-40.

Ellie Beauprez, Anne-Cécile Caron, Maxime Morge, Jean-Christophe Routier. Réaffectation de tâches de la théorie à la pratique : état de l’art et retour d’expérience. Vingt-neuvièmes journées francophones sur les systèmes multi-agents (JFSMA), Jun 2021, Bordeaux, France. pp.51-60.

Ellie Beauprez, Anne-Cécile Caron, Maxime Morge, Jean-Christophe Routier. A Multi-Agent Negotiation Strategy for Reducing the Flowtime. 13th International Conference on Agents and Artificial Intelligence, Feb 2021, Online streaming, Spain. pp.58-68.

Ellie Beauprez, Anne-Cécile Caron, Maxime Morge, Jean-Christophe Routier. Stratégie multi-agents de négociation pour la réduction du flowtime. Rapport de recherche. Université de Lille, 2020.

License

This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with this program. If not, see http://www.gnu.org/licenses/.