Sites Inria

Version française

MEXICO Research team

Modeling and Exploitation of Interaction and Concurrency

Team presentation

In the increasingly networked world, reliability of applications becomes ever more critical as the number of users of, e.g., communication systems, web services, transportation etc grows steadily. MExICo works towards a better understanding and an increased reliability of distributed and asynchronous systems, and focuses its research on the two features of Concurrency and Interaction. The increasing size and the networked nature of communication systems, controls, distributed services et.c 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.

Research themes

  • Diagnosis and diagnosability. In diagnosis for discrete event systems, the task is to determine - from observations of streams of event labels - whether faults have occurred 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:
    • Unfolding- based diagnosis
    • Observabilité et diagnosticabilité
    • Decentralized diagnosis
  • Test. Let an formal specification model M and an implementation I, that supposedly conforms to M, be given; I's behavior 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.
    • In asynchronous testing, one centralized tester applies nonsequential inputs and observes partially ordered outputs on different ports.
    • In local testing, several processes send test messages to their peers and observe locally the received response; the testing problem consists in determining global conformance from the local test results.
  • Controller 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 behavior 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:
    • Abstraction
    • Composition
    • Adaptation
  • Fields of Application
    • Traffic security
    • Adaptation for web service composition
    • Telecommunication

International and industrial relations

  • EMoTiCon: Equivalences between Models with Time and Concurrency. Project of the Farman institute of ENS Cachan with LURPA (laboratory for automated production at ENS Cachan).
    • SMYLE: EGIDE/DAAD (Procope 2008/2009), with M\"unchen and Aachen, on bridging the gap between requirements, provided as a set of MSCs, and conforming design models.
    • Strong links and exchanges with Chennai Mathematical Institute (CMI), India; ARCUS.
    • ANR project DOTS (distributed, open and timed systems) with IRCCyN, IRISA, LaBRI, LAMSADE.
    • Participation in European project Disc (distributed supervisory control of large plants) with academic and industrial partners in France, Italy, the Netherlands, Belgium, Germany and the Czech Republic.
    • ANR project Checkbound with LACL, LAMSADE, LIG, LSV, INT, PRISM on model checking for performability and security of computer systems.
    • Several other academic cooperations with Leipzig, Duisburg, Padova, Bordeaux, Milan etc.

    Research teams of the same theme :

    • Inria Headquarters and research centres

    Direct links


    Resources