Until recently, resource allocation algorithms (routing, scheduling, etc.) were mainly designed in three different information settings: (I) the clairvoyant setting in which all the parameters (volumes, arrival instants,…) of the tasks are known in advance; (ii) the non-clairvoyant setting where the parameters are unknown; (iii) and finally the stochastic setting where the algorithm is fed with the distribution of the parameters.

The recent trend in data collection has made a fourth setting interesting. By running ML algorithms on the datasets containing parameters from previous instances, one can get an estimate (or predictions) of the parameters of the new tasks. The principal research question that arises is how to design algorithms that take into account predictions. If the predictions were accurate, we could use the clairvoyant algorithms. On the other hand, if the predictions were completely useless, we could fall upon non-clairvoyant algorithms. However, when the predictions are known up to a certain degree of accuracy, it is not entirely clear whether existing algorithms can be applied off the shelf or new algorithms will be needed.

This thesis will investigate prediction-based resource allocation for coflow scheduling which has its origins in datacenters. A coflow is a collection of subtasks each of which has to be finished before the coflow can be marked as done. This model of coflows differs from the traditional flow model in which a task does not have subtasks. Scheduling of coflows with the objective of minimizing the average coflow completions times has been widely studied in the clairvoyant as well as non-clairvoyant setting, and approximation algorithms are known.

Our contributions will be to design approximation algorithms for when predictions are given instead of the actual values. The algorithms should be consistent, that is behave almost as well as the best clairvoyant algorithms when the predictions are accurate, and robust, that is maintain worst-case guarantee even with terrible predictions.

Host laboratory: the thesis will be carried out within the SARA team of LAAS-CNRS, Toulouse, France. It will be supervised by Olivier BRUN and Balakrishna PRABHU.

Starting date: 02 September 2024.

Application material: should include a CV, a motivation letter, mark sheet for the last two years and the names of one or two persons who can write a recommendation letter for the candidate.

Contacts (for sending the application material or for queries): Olivier BRUN (brun@laas.fr) et Balakrishna PRABHU (balakrishna.prabhu@laas.fr).