MEXICO : Modelling and Exploitation of Interaction and Concurrency

Research Topics

In the increasingly networked world, reliablity of applications becomes ever more critical as the number of users of, e.g., communication systems, web services, transportation etc grows steadily. MExICo will work towards a better understanding and an increased reliability of distributed and asynchronous systems, and thus join the existing effort of many other teams that use formal methods; what is particular in the present proposal is that our team focusses its research on the two features of concurrency and interaction.

Members

Membres permanents

Thomas Chatain
Maître de conférences, ENS Cachan
Stefan Haar
Directeur de recherche, INRIA Saclay-Île de France
Stefan Schwoon
Maître de conférences, ENS Cachan
Matthias Függer
Chargé de recherche, CNRS
Serge Haddad
Professeur, ENS Cachan
 
Laurent Fribourg
Directeur de recherche, CNRS
Claudine Picaronny
Maître de conférences, ENS Cachan

Membres détachés, associés ou temporaires

Larissa Fischer
Étudiante M1
Adrien Le Coënt
Doctorant au CMLA
 

Doctorants

Yann Duplouy
Doctorant, IRT SystemX
Engel Lefaucheux
Doctorant, ENS Cachan (coencadrement à l'IRISA, Rennes)
Tymofii Prokopenko
Doctorant (co-encadrement à Polytechnique)
Juraj Kolcak
Doctorant, ANR-FNR AlgoReCell
Hugues Mandon
Doctorant, Inria
Adnane Saoud
Doctorant, Digicosme projet Emergence CODECSYS (co-encadrement au L2S)

Detailed Presentation

The increasing size and the networked nature of communication systems, controls, distributed services etc. confront us with an ever higher degree of parallelism between local processes. For any form of analysis and control, a global view of the system state leads to overwhelming numbers of states and transitions, and blurs the mechanics that are at work rather than exhibiting them. Conversely, respecting concurrency relations avoids exhaustive enumeration of interleavings, and allows to focus on 'essential' properties of nonsequential processes characterized by causal precedence relations. We see concurrency in distributed systems as an opportunity rather than a nuisance that leads to state space explosion in the formal models and slows down algorithms.

Diagnosis and Diagnosability

In diagnosis for discrete event systems, the task is to determine - from observations of streams of event labels - whether faults have occured in the system under observation. Diagnosis algorithms have to operate in contexts with low observability, i.e., in systems that exhibit many events invisible to the supervisor. Checking observability and diagnosability for the supervised systems is therefore a crucial and non-trivial task in its own right. MExICo works on the following aspects:

Testing

Let a formal specification model M and an implementation I, that supposedly conforms to M, be given; I's behaviour is influenced by the input streams received, and observable only via an output stream. Conformance testing consists in computing - whenever possible - input streams that allow to determine whether I deviates from M or conforms to it. MExICo's research is on testing for distributed asynchronous systems.

Dynamic and Parameterized Communicating Systems

Many distributed programs do not depend on a fixed network topology, but shall be run on arbitrary architectures such as star topologies, bus topologies, trees, grids, or rings. They may also generate their communication topology dynamically at runtime. We aim for high-level specification formalisms and automata models that support the synthesis and formal verification of such systems.

Controler Synthesis

In a distributed setting, we need to synthesize a distributed program or distributed controllers that interact locally with the system components. The main difficulty comes from the fact that the local controllers/programs have only a partial view of the entire system. It is essential to specify expected properties directly in terms of causality revealed by partial order models of executions (MSCs or Mazurkiewicz traces).

Adaptation and Grey Box Management

Contrary to mainframe systems or monolithic applications of the past, we are experiencing and using an increasing number of services that are performed not by one provider but rather by the interaction and cooperation of many specialized components. As these components come from different providers, one can no longer assume all of their internal technologies to be known (as it is the case with proprietary technology). Thus, in order to compose e.g. orchestrated web services, to determine violations of specifications or contracts, to adapt existing services to new situations etc, we have to analyze the interaction behaviour of components known only through their public interfaces, thus semi-transparent and semi-opaque; we refer to them as "grey boxes". Three central issues emerge:

National and International Collaborations

Ongoing projects

Past projects:

À propos du LSV

À propos de MExICo

Une équipe commune avec

Logo INRIA Saclay

Présentation de MExICo (2013)

Présentation de Mexico à l

Groupe de travail Vasco-Mexico

No entries.

Publications récentes

Toutes les publications de l'axe MEXICO

B. Bollig, M. Fortin and P. GastinCommunicating Finite-State Machines and Two-Variable LogicIn STACS'18, Leibniz International Proceedings in Informatics. Leibniz-Zentrum für Informatik, February 2018. To appear. Web page | BibTeX )
H. Mandon, S. Haar and L. PaulevéTemporal Reprogramming of Boolean NetworksIn CMSB'17, LNBI 10545, pages 179-195. Springer-Verlag, September 2017. PDF | BibTeX )
M. Függer, Th. Nowak and M. SchwarzBrief Announcement: Lower Bounds for Asymptotic Consensus in Dynamic NetworksIn DISC'17, Leibniz International Proceedings in Informatics. Leibniz-Zentrum für Informatik, October 2017. Web page | BibTeX )
G. Tarawneh, M. Függer and C. LenzenMetastability Tolerant ComputingIn ASYNC'17. IEEE Computer Society, May 2017. To appear. BibTeX )
M. Függer, A. Kinali, C. Lenzen and T. PolzerMetastability-Aware Memory-Efficient Time-to-Digital ConverterIn ASYNC'17. IEEE Computer Society, May 2017. To appear. PDF | BibTeX )

Toutes les publications de l'axe MEXICO