STIC-AMSUD GENE

Stochastic dynamics of large games and networks 



Project goals

The GENE project aims at contributing to the theory of the performance evaluation and control of modern communication networks, using tools of game theory, especially the so-called mean field games, probability theory and control theory.

The research to be developed aims at combining different tools from quite different disciplines: scaling limits of stochastic processes, games dynamics and control theory, to obtain new insights significant contribution in the applied field of load balancing, resource allocation and decentralized control. A specific attention will be given to the notion of load balancing which is one of the hottest topics in applied mathematics in the last 3 years.

The expertise of the different partners in these areas definitely forecasts a strong contribution to the current state-of-the-art.

 

The main objectives of the GENE project are:
(i) to consolidate an already strong research and education relationship between the Probability group of the university of Buenos Aires (UBA, Argentina), the Engineering Faculties of UDELAR (Universidad de la República Uruguay) and ORT (ORT university) in South America and the CNRS (LAAS Toulouse) and the INRIA (MESCAL Grenoble) in France.
(ii) to boost and to promote research bonds between the main research and graduate/post-graduate education institutions in Argentina and Uruguay (Universidad de Buenos Aires, UDELAR, ORT), as well as to expand the South American-French historical scientific collaboration by including both CNRS and INRIA, the major pillars of French scientific development.

The common roadmap for reaching these goals will be: (i) to organize project workshops and internships in partner institutions in order to build a common knowledge map and common tools in the field of performance evaluation and optimal control of information systems and communication networks (ii) to disseminate joint results by publications in major international conferences or journals, (iii) to develop common guidance of PhD and postdocs.    

Scientific achievements

UBA-UdelaR
The collaboration between UBA and UdelaR carried out during 2018 was focused on the analysis of sequential exploration algorithms on large random graphs. In particular, we characterized a family of random graphs where the simple (and classic) degree-greedy exploration algorithm obtains a maximum independent set (i.e. no two vertices in the set are connected in the original graph). The problem of finding a maximum independent set has several important applications, in particular in telecommunications, where it is related to the capacity of the underlying wireless network.
Moreover, we have derived the fluid limit corresponding to the degree-greedy algorithm on sparse random graphs. The corresponding differential equation may be thus used to estimate the capacity of large wireless networks.
This work has been accepted for presentation in the upcoming 36th International Symposium on Computer Performance, Modeling, Measurements and Evaluation 2018 (Toulouse, France), as well as on the journal Performance Evaluation Review. We are currently working on an extended version of the work to be submitted to Stochastic Systems.





 UBA-CNRS

Redundancy is a technique introduced in computer systems with the aim of reducing response times. The basic idea is to make copies of a job and dispatch them into multiple servers at the same time. When the first copy of a job completes service, the rest of the copies are removed even if they did not complete service. This means that a redundant job gets the shortest of multiple service times. We have analysed the stability region of K server Markovian systems where copies are dispatched into d servers uniformly at random and all the copies of a job are identical (i.e. have the same service time) under service policies PS, FCFS and ROS. There have been several analysis in literature under the condition that copies are i.i.d., where it is proven that these systems are maximum stable. One of our goals has been to prove that under identical copies assumption  (which we think is a better approach of reality) the stability condition reduces considerably. We have proved that under PS service policy, the stability condition reduces to the worst possible.

In the future we aim to fully characterize the stability condition of FCFS models with redundant request, analyse the mean response times and the stability of system that have other redundancy structures.


Scientific production

In preparation:

On the stability of redundancy models with FIFO scheduling,

Elene Anton (IRIT-CNRS),

Ina Maria Verloop (IRIT-CNRS),

Matthieu Jonckheere (University of Buenos Aires),

Urtzi Ayesta (CNRS-IRIT and Ikerbasque/Univ. Basque Country)

Submitted:

On the stability of redundancy models,
Elene Anton (IRIT-CNRS),
Ina Maria Verloop (IRIT-CNRS),
Matthieu Jonckheere (University of Buenos Aires),
Urtzi Ayesta (CNRS-IRIT and Ikerbasque/Univ. Basque Country)

 
Published:
Degree-Greedy Algorithms on Large Random Graphs
Authors: Paola Bermolen (Universidad de la República, Uruguay)
Matthieu Jonckheere (University of Buenos Aires- Conicet)
Federico Larroca (Universidad de la República, Uruguay)
Manuel Saenz (University of Buenos Aires- Conicet)

accepted in Performance 2018,






International coordinator: Matthieu Jonckheere,

 
LIST OF PARTICIPANTS

Universidad de la República, Montevideo, Uruguay
Coordinator: Prof. Federico Larroca,
Prof. Paola Bermolen, 
Valeria Goycoechea, PhD student.

Universidad ORT
Coordinator: Prof Andres Ferragut,
Prof Fernando Paganini,
Diego Goldsztajn, PhD student

Universidad de Buenos Aires, ArgentinaCoordinator: Prof. Matthieu Jonckheere,
Prof. Ines Armendariz,
Prof. Pablo Ferrari,Prof. Pablo Groisman,

Emmanuel Ferreyra (PhD student)
Manuel Saenz (Phd student)
Maximilainao Altamirano (PhD student)


CNRS, Toulouse, France,
Coordinator: Dr Balakrishna PrabhuDr.
Dr Urtzi Ayesta (LAAS-CNRS),
Dr Maaike Verloop, (IRIT-CNRS),
Elene Anton, (IRIT-CNRS), PhD student
Santiago Duran, (IRIT-CNRS), PhD student