Direction des Relations Internationales (DRI)

Programme INRIA "Equipes Associées"



DST : Distributed systems,  Supervision and Time.




Equipe-Projet INRIA : Distribcom & S4

Organisme étranger partenaire : National University of Singapore

Organisme étranger partenaire :

Chennai Mathematical Institute

and Institute for Mathematical Science.

Centre de recherche INRIA : INRIA Rennes Bretagne Atlantique



Pays : INDIA



Coordinateur français

Coordinateur étranger

Coordinateur étranger

Nom, prénom

 Hélouët, Loïc

 P.S. Thiagarajan

Madhavan Mukund





Organisme d'appartenance
(précisez le département et/ou le laboratoire)

INRIA Rennes, Bretagne Atlantique

Equipe Distribcom

 National University of Singapore (NUS)

Chennai Mathematical Institute

Adresse postale


Campus de Beaulieu,

35042 Rennes Cedex,


School of Computing
National University of Singapore
Computing 1, Law Link
Singapore 117590
Republic of Singapore

Chennai Mathematical Institute
Plot H1, SIPCOT IT Park
Padur PO, Siruseri 603103




 33 2 99 84 75 90

 +65 6874 7998

+91 44 2747 0226-0229


 33 2 99 84 71 71


+91 44 2747 0225


La proposition en bref

Titre de la thématique de collaboration (en français et en anglais) :  DST  - Distributed systems : Supervision and Time

Descriptif : This associated team is a tripartite collaboration between two projects at INRIA Rennes (S4 & Distribcom), the National University of Singapore (NUS), and two institutes in Chennai (INDIA), the Chennai Mathematical Institute (CMI) and the Institute of Mathematical Sciences (IMS). The objective of the DST project is to study distributed systems, supervision and time issues with the help of concurrency models. The two main themes of the project are supervision, and quantitative/timed aspects of systems. The supervision theme will focus on distributed scheduling policies of distributed systems to ensure satisfaction of some properties (preservation of some bound on communication channels, for instance), diagnosis, and distributed control techniques. The second theme on time aspects of distributed systems will focus on the analysis of qualitative and quantitative properties of timed systems and models. The quantitative approaches will rely on network calculus applied to multimode Real Time Calculus, and the timed models studied during the collaboration will be inspired from timed scenarios. We expect some interaction between the two themes, that is improve timed characteristics (throughput, …) using supervision techniques, or conversely use some knowledge of time in a system to perform more accurate diagnosis and supervision.

Présentation détaillée de l'Équipe Associée

1. Objectifs scientifiques de la proposition

This associated team is a tripartite collaboration between two projects at INRIA Rennes (S4 & Distribcom), the National University of Singapore (NUS), and two institutes in Chennai (INDIA), the Chennai Mathematical Institute (CMI) and the Institute of Mathematical Sciences (IMS). The objective of the DST project is to study distributed systems, supervision and time issues with the help of concurrency models. The two main themes of the project are supervision, and quantitative/timed aspects of systems. The supervision theme will focus on distributed scheduling policies of distributed systems to ensure satisfaction of some properties (preservation of some bound on communication channels, for instance), diagnosis, and distributed control techniques. The second theme on time aspects of distributed systems will focus on the analysis of qualitative and quantitative properties of timed systems and models. The quantitative approaches will rely on network calculus applied to multimode Real Time Calculus, and the timed models studied during the collaboration will be inspired from timed scenarios. We expect some interactions between the two themes, that is improve timed characteristics (throughput, …) using supervision techniques, or conversely use some knowledge of time in a system to perform more accurate diagnosis and supervision.


Theme 1 : Supervision and control


We want to address two main themes: the first one is supervisory control, i.e. calculus of a controller or a set of controllers supervising a system, so that the monitored system satisfies some given properties. The second one is scheduling, that is finding adequate order for the activation of autonomous component such that some objectives are always fulfilled.


  • Supervisory control : The idea in supervisory control is to guide a system so that it reaches a goal or stays in a legal set of behaviors. The technique used is to compute a machine (also called a controller) that can observe the system, and forbid some actions to its components. Control has been well studied since [RW89], but in a centralized setting, that is observation and control of the system is done by a single centralized controller. The new challenges are now to consider the problem in a distributed world, that is control a system via a set of local and independent controllers, each of them with a partial observation of the whole system. Distributed control has been shown undecidable in the general case [Tripakis01], but distributed solutions can be implemented, either with some restrictions to the architecture (allowed observations, controlled actions, etc), on the control objectives, or when distributed supervisors are allowed to communicate. Several objectives have been identified :


    • Distributed control with tagged messages: we propose to investigate the particular case of distributed control, where communication among distributed controllers can only take place whenever the system under control communicates (that is by piggy-backing some control information on the message of the system), and the control objective are the fair scheduling of a set of distinguished transitions of the plant and the boundedness of all communication buffers.
    • Distributed control with minimal messages: as already mentioned, distributed control is undecidable, but can find a solution when the distributed supervisors are allowed to communicate. However, these communications should not impose time penalties, or be too verbose if the communication network used between the supervisors is the same as the network used by the supervised system. Another research direction is then the development of distributed control and diagnosis synthesis techniques minimizing, for a given set of ultimately periodic trajectories, the amount of information that has to be exchanged between the supervisors. In particular, the paradigm of distributed games could be used to generate the controllers.
    • Control with true concurrency models: very often, control objectives are given under the form of a finite state machine, the main objective being to maintain the behaviors of a system (also given as a finite state machine) inside this regular description. The controllers are usually computed using complementation and products of the finite state machines. A challenging idea is to transpose this control problem to true concurrency models. A step in this direction was proposed for asynchronous transition systems in [MTY05]. One may for instance want to control a plant such that it stays in a MSC language, or conversely an MSC description (preferably a specification that can be implemented) so that it stays in some regular language. This involves at the same time some control and some scheduling among processes. Some work has been initiated on this topic by Laurie Ricker and Benoit Caillaud. However, these techniques will clearly have limitations, as specifications given under the form of Message Sequence Charts, for instance, are not regular languages, and hence products or complementations are not necessarily computable.
    • Distributed control with games: the distributed control problem can also be addressed using distributed games [WM03]. Two-player games consitute a useful theoretical tool for the study of centralized synthesis problems. Analogously, in the context of distributed synthesis, we can use the model of distributed games, or of games with imperfect information. However in general distributed games are neither determined nor algorithmically solvable. Restricting the modes of communications between players to obtain tractable subclasses of games is challenging and holds prospects for new questions in distributed control to be addressed.


  • Scheduling: Scheduling can be considered as a weakened version of supervisory control, and consists in specifying parts of a system separately, and ensure some good properties by activating processes in the system according to a given strategy. Controllers can forbid actions to reach a goal, scheduling policies can only postpone them. Good scheduling policies for distributed embedded applications are required to meet hard real time constraints and for optimizing the use of computational resources. We want to produce distributed scheduling policies, that is, scheduling should result from local monitors. In a recent work, [DGTY08], we have studied the quasi-static scheduling problem (QSS) in which (uncontrollable) control flow branchings can influence scheduling decisions at run time. By definition of QSS, this scheduling is given globaly. The QSS problem has been introduced by people from Cadence (Kondratyev et al.) to optimize circuits obtained from asynchronous specifications. The idea was that asynchronous specifications are easier to give, since they are compositional. However, some hard work has to be performed to turn automatically these specifications into circuits. The major lock is that without restriction, the asynchrony among components often leads to communication channels being unbounded, with the consequence that the system can not be implemented. One thus needs some smart policy in order to keep every choice of each device feasible, while keeping the channels bounded. The only parameter the implementation can play with is thus time: it cannot forbid actions, but it can postpone them. That is, what one is looking for is a scheduling policy. The abstract task model that we studied consists of a network of sequential processes that communicate via point-to-point buffers. In each round, a task is activated by a request from the environment. When the task has finished computing the required responses, it reaches a pre-determined configuration and is ready to receive a new request from the environment. For such systems, we have proved that determining existence of quasi-static scheduling policies is undecidable. However, the problem is decidable for the important sub-class of "data branching" systems in which control flow branchings are due exclusively to data-dependent internal choices made by the sequential components, and not because of choice between which channels to receive from. The challenge is now to restate the quasi-static scheduling problem as a local monitor problem. This would improve the solution in two ways. First, obtaining a scheduling policy guarantees that it can be implemented in a distributed way. Second, one might obtain decidability for all systems, and not only for data branching systems. It may seem paradoxical, since there are fewer systems which can be scheduled by distributed monitors than systems which are quasi static schedulable. However, those systems which are schedulable globally but not with distributed monitors seem to be the source of undecidability of QSS for general systems (ie non data branching).



Theme 2 : Time


The second theme addressed by the DST project is time in distributed systems. We want to address time from three points of view. The first one is the study of quantitative aspects, using techniques such as (Max,+) algebra, and the network calculus, for which both Distribcom and NUS have strong competences. The second aspect is the modelling power of timed model: several members of Distribcom and of CMI are very involved in research around Message Sequence Charts, a true concurrency model based on composition of partial orders. This model has been extended with time recently, and raises new challenges. The third aspect is the use of time as additional information for supervision.

·        Quantitative aspects : an important aspect in the analysis of systems is the study of the worst-case bounds for their performances. Some performance oriented models such as Network Calculus have already been proposed for static analysis. Within this setting, a system is seen as interconnected servers that treat incoming requests according to a service policy. However, with this model, the parameters of a system never change: arrival and service policies of servers do not evolve with time. Some models where these parameters can change have been proposed, such as event count automata and multimode Real time calculus. Event-count automata count the number of events that can happen at each time. In each state, the number of events is lower and upper bounded. Transitions are conditioned to some guards on counters, and when a transition is fired, some counters can be reset. These models are equivalent to timed-automata, and hence their analysis can lead to state-space explosion. During the CASDS collaboration, we have studied an intermediate model called the "multimode Real Time Calculus": arrival processes obey to some Network Calculus constraints, but these constraints can change from time to time. This is modeled by two finite automata (an arrival automaton and a service automaton), whose states can change with transitions between states caused by different signals. In the arrival automaton, an arrival curve is associated to each state, as well as a time interval where the state can change. Moreover, transitions can be guarded by some predicates depending on the parameters of the systems (fill-level for example). The service automaton is defined similarly, with service functions. We have first tried to find some efficient ways of analysing these multimode systems. Two models can be efficiently analysed: when the arrival and service automata are synchronous (the automata change their state exactly at the same time) and when they are totally asynchronous (one can find an equivalent arrival curve and an equivalent service curve). We plan to continue the work on this kind of model, and extend the analysis to cases where automata are not purely synchronous or purely asynchronous, but rather a mix of both models. The solution to find efficient analysis techniques could be to mix the two approaches used in the synchronous and asynchronous cases. 


·        Timed concurrent models and their properties: We propose to study properties of timed concurrent models, and more precisely of timed scenarios. A recent extension that adds time constraints to Message Sequence Charts (MSCs) have been proposed [AMN07]. This new model also brings several new challenges. For instance, checking time constraints on timed MSCs is an undecidable problem in general, and a solution have been proposed for the class of regular MSC languages. An interesting challenge is to study if timed constraints checking applies to other MSCs outside this class. The difficulty is to find a way to verify these constraints over a regular set of representants. However, in the general case, unbounded MSCs with generic constraints can be used to encode two counter machines, leading to undecidability. Another question is whether the timing constraints imposed on an MSC make executions channel-bounded. In general, this question is also undecidable, but there could be a solution for a restricted class of constraints. Note that timed scenarios are seen as a starting point, but that several other true concurrency models might be studied, such as communicating automata, traces….


·        Channels with losses : nowadays, MSCs only describe messages that are lost + found, or necessarily received. However, in realistic communication protocols, messages that arrive too late can also be declared obsolete. According to the MSC terminology, such messages are received. An interesting question is then to consider messages that are sent, and forgotten if not received in time. This model also differs from models with lossy channels, as losses here do not depend on a probability, but rather on time thresholds. Such model has never been proposed, but we have the intuition that this extension could be done using the extended MSCs of Martin Leucker [Leucker02].


·        Timed diagnosis : So far, very few work address diagnosis with time [Chatain06]. By diagnosis, we mean the following problem. A distributed system is equipped by sensors (either material part or code instrumentation) that send some observations to a supervisor. These observations are collected to form a partial view of an execution of the system. The question addressed by diagnosis is, from a given observation O of the system and a model M, find every explanation of the observation compatible with O. Several approaches have been proposed, using automata or Petri nets as models. Thomas Chatain has proposed a technique based on Timed Petri nets unfoldings. In a recent work, we have proposed an untimed scenario-based approach [HGG06]. The interest of this approach is to compute a finite representation of all possible explanations for an observation under the form of a High-level MSC. An interesting extension to this work would be now to consider diagnosis from scenarios with time, that is use the information on the execution dates of some events in the observation and the time constraints in the scenario model to refine diagnosis.




In addition to these two main themes, we expect some cross-theme works. For instance, we are interested in supervision techniques that would allow to maintain a given quality of service. Using quantitative information on the model may also be useful to get more efficient algorithms for control and to have a more accurate view of the behaviors of the systems.



[Chatain06] Th. Chatain, Dépliages symboliques de réseaux de Petri de haut niveau et application à la supervision des systèmes répartis.  Thèse de doctorat, Université Rennes 1, Rennes, France, November 2006.

[AMN07] S. Akshay, M. Mukund, K. Narayan Kumar, Checking Coverage for Infinite Collections of Timed Scenarios. CONCUR 2007: 181-196

[RW89] P.J.G. Ramadge and W.M. Wohnham, The control of discrete event systems. Proceedings of the IEEE, 77(1):81–98, 1989.

[Tripakis01] S. Tripakis, Undecidable Problems of Decentralized Observation and Control. In IEEE Conference on Decision and Control, 2001.

[DGTY08] P. Darondeau, B. Genest, P.S. Thiagarajan, S. Yang : Quasi-Static Scheduling of Communicating Tasks. CONCUR 2008, 310-324, LNCS 5201.

[Leucker02] B. Bollig, M. Leucker, P. Lucas, Extending Compositional Message Sequence Graphs. LPAR 2002: 68-85

[HGG06] L. Hélouët, T. Gazagnaire, B. Genest, Diagnosis from scenarios, Proc. of WODES'06.

[MTY05] P. Madhusudan, P.S. Thiagarajan, S. Yang, The MSO theory of connectedly communicating processes , Proc. of FSTTCS05.

[WM03] I. Walukiewicz and S. Mohalik, Distributed games. In FSTTCS ’03, LNCS 2914, pages 338–351. Springer, 2003.


2. Présentation des partenaires

INRIA Rennes Bretagne Atlantique

On the INRIA side, the list of researchers involved in this collaboration is: Loïc Hélouët, Blaise Genest, Anne Bouillard from the Distribcom Team, and Philippe Darondeau, Benoit Caillaud for the S4 team.

The french coordinator of this collaboration will be Loïc Hélouët.

Loïc Hélouët is Chargé de Recherche 1ère classe at INRIA Rennes. He received his PhD in 2000 from Université de Rennes 1. He worked one year In France Telecom’s research center in Lannion before joining INRIA in 2001. He is rapporteur at the International Telecommunication Union for the questions on Message Sequence Charts and on the requirements languages. He was coordinator for the CASDS associated team during the 2006-2008 period. His research interests include true concurrency models, scenarios, and distributed systems.


National University of Singapore

On the NUS side, the list of researchers involved is: P.S. Thiagarajan and  Phan Thi Xuan Linh. The Coordinator of the collaboration for NUS will be P.S. Thiagarajan.

P.S. Thiagarajan received his B.Tech (Electrical Engineering) from the Indian Institute of Technology (IIT), Madras (1970) and his Ph.D. in Computer Science from Rice university, Houston, Texas, USA (1973). He has been a Research Associate at Project MAC (the predecessor of the current Laboratory for Computer Science), Massachusetts Institute of Technology (MIT) (1973-1975), a Research Scientist at the Gesellschaft für Mathematik und Datenverarbeitung, St. Augustin, Germany (1975-83), a Lektor (Associate Professor) at the Computer Science Department of Aarhus University, Aarhus, Denmark (1983-86), an Associate Professor at The Institute of Mathematical Sciences, Chennai, India (1986-89) and a Professor at the Chennai Mathematical Institute (1989-). He was a visiting professor in the School of Electrical and Computer Engineeering, Georgia Institute of Technology, Atlanta, USA during 2000-2001 and a visiting professor in the Computer Science Department of NUS during 2001-2002 where he is currently a professor. He has been an invited speaker at a variety of international conferences, has lectured in a number of advanced courses and has held visiting professorships around the world. He is a member of the editorial boards of the journals Theoretical Computer Science and the International Journal on Foundations of Computing. He served two terms (1997 - 2003) as a member of the Governing Council of the European Association for Theoretical Computer Science (EATCS). He is a Fellow of the Indian Academy of Sciences and the Indian National Academy of Sciences.


In Chennai the list of involved researchers is: Madhavan Mukund (professor at CMI), Narayan Kumar (professor at CMI), Ramaswamy Ramanujam(professor at IMS), Akshai Sundararaman (PhD Student at CMI+ ENS Cachan). The Indian coordinator for the project will be Madhavan Mukund.

Madhavan Mukund is professor at the Chennai Mathematical Institute. He received his B.Tech (Computer Science and Engineering) from the Indian Institute of Technology (IIT), Bombay in 1986, and a PhD in Computer Science from Aarhus University in 1992. His research interests include formal methods for specification, verification and testing, partial order based models of concurrent systems, temporal logics. He is Secretary and Member of the  Executive Council of the Indian Association for Research in Computing Science (IARCS) , member of the EATCS Council, (European Association for Theoretical Computer Science.), and  National Coordinator of the  Indian Computing Olympiad. He is also member of the Editorial Board of  the Formal Methods Letters and Transactions on Petri Nets and Other Models of Concurrency (ToPNoC) journals.



History of past collaborations:

Our research interests have had a substantial overlap for a long period of time. Frequent interactions have taken place during international conferences/workshops, and the three groups have had similar research interests for the last decade, as exemplified by reciprocal citations of our publications. The three teams have a long collaboration history, and interest in similar research topics for a long time:

·         Philippe Darondeau, Benoît Caillaud and P.S. Thiagarajan have both been working on techniques of regions for nets, automata, and languages. P.S. Thiagarajan has worked more on the theoretical side, and the INRIA team more on the algorithmic side.

·         Philippe Darondeau, Eric Badouel and P.S. Thiagarajan have both worked on regular trace event structures.

·         Madhavan Mukund, Narayan Kumar in Chennai, P.S. Thiagarajan in NUS, Loic Hélouet, Philipe Darondeau and Blaise Genest in Rennes have all worked on the topic of Message Sequence charts this last decade. 

·         S4 and NUS have had close research activities on the topic of controller synthesis.

·         P.S. Thiagarajan has been one of the external referees of Blaise Genest and Thomas Gazagnaire’s PhD thesis.

P. S. Thiagarajan has strong connections with the Chennai Mathematical Institute (CMI) and with the Institute of Mathematical Sciences (IMS).


Furthermore, more formalized collaborations already occurred in the past.

·         Philippe Darondeau participated in the past to an INRIA-Chennai joint cooperation (INRIA leader Gérard Boudol, UR Sophia-Antipolis).

·         Since 2006, Distribcom, S4 and the NUS have been working in the associated team CASDS. The Chennai partners joined this collaboration in 2008. During this 2006-2008 period, several exchanges took place: each permanent member in the team accomplished at least one visit to one of the partners. A PhD student of Distribcom, Thomas Gazagnaire, spent 3 months at NUS, and a former PhD student of NUS, Shaofa Yang, held a post doc position in the Distribcom team during two years. The CASDS associated team has led to the two common publications listed below. Three other common works have been submitted for publication.

[GGHTY07] T. Gazagnaire, B. Genest, L. Hélouët, P.S. Thiagarajan, S. Yang, Causal HMSCs, CONCUR 2007, 166-180, LNCS 4703.

[DGTY08] Ph. Darondeau, B. Genest, P. S. Thiagarajan, S. Yang: Quasi-Static Scheduling of Communicating Tasks. CONCUR 2008, 310-324, LNCS 5201.



3. Impact

The three groups in Chennai, Rennes and Singapore share common interest for concurrency models and supervision of distributed systems, and this associated team should provide ground for new achievements in our common fields of competence. We have already collaborated in the past at the occasion of the CASDS associated team (2006-2008), and this collaboration was successful on several points. First of all, it was a good opportunity to send students working abroad. Several exchanges of student took place: Thomas Gazagnaire, Phd Student in the Distribcom Team spent 3 months in Singapore, and Shaofa Yang, former student at the NUS spent two years at INRIA Rennes on a post-doc position. Then, CASDS was also the occasion of new contacts: our Indian partners in DST joined CASDS in 2008. The funding of DST should allow the three teams to conclude the work initiated in 2008, to strengthen the collaboration between INRIA, NUS, and Chennai institutes, and to tackle the long term research objectives detailed in this proposal. The CASDS associated team was also a fruitful collaboration in terms of publications, and we can expect DST to be as productive.


This associated team is also the occasion to benefit from the expertise of the partners. Specific domains of competence are respectively:

·        Diagnosis for INRIA

·        Timed concurrency models for Chennai

·        Distributed games for NUS


4. Divers :

One interesting aspect for the INRIA side is the fact that NUS has excellent access to very good students from China, and that the collaboration with the two institutes in Chennai would also give INRIA the opportunity to welcome very good students from India.


Programme de travail


The proposed work programme can be summarized as follows:

·        Supervisory control: study distributed supervisory control problems with tools such as scenarios, distributed games,…

·        Scheduling: restate the quasi static scheduling problem of [DGTY08] with local monitors.

·        Timed Scenarios: pursue work on properties of timed scenarios: find solutions to extend model checking of timed properties to a larger class of High-level MSCs than in [AMN07]

·        Quantitative analysis of time: pursue work on quantitative analysis of time for multimode Real Time Calculus with models that are not purely synchronous or asynchronous.

·        Timed diagnosis: extend the work on scenario-based diagnosis to include timed considerations.

·        Timed extensions of true concurrency models: study new timed extensions to deal with ignored messages in scenarios.


Programme d'échanges avec budget prévisionnel

1. Echanges

For year 2009, the following visits are planed:

Person / Dates



Accomodation & subsistence


Blaise Genest – CR2 (second part of 2009)

15 days

1600 Eur

2000 Eur

3600 Eur

P.S. Thiagarajan – Professor (January 2009?)

15 days

1600 Eur

2000 Eur

3600 Eur

Anne Bouillard, - (MdC) visit to NUS  (Summer 2009)

15 days

1600 Eur

2000 Eur

3600 Eur

M. Mukund – Professor

15 days

1600 Eur

2000 Eur

3600 Eur

N. Kumar – Professor

15 days

1600 Eur

2000 Eur

3600 Eur

R. Ramanujam – Professor

15 days

1600 Eur

2000 Eur

3600 Eur

Summer internship at INRIA Rennes

2 months

1600 Eur

2000 Eur

3600 Eur





25200 Eur




Nombre de personnes

Coût estimé

Chercheurs confirmés












Autre (précisez) :








Nombre de personnes

Coût estimé

Chercheurs confirmés












Autre (précisez) :






2. Cofinancement

·        CMI and IMS in Chennai have a French-Indian collaboration named Timed-Discoveri. This collaboration ends this year, and the amount that will be available for this project in 2009 is not yet clear. If some funding is still possible in 2009, we plan to factorize the visits of researchers from Chennai at the occasion of this collaboration with visits to Rennes. Moreover, Akshay Sundaraman receives a scholarship from MENRT for his thesis between Chennai, India and Cachan, France. It provides 22 k Euros for 2009.

·        Both S4 and Distribcom are involved in DISC: Distributed Supervisory Control of Large Plants, an european project of the 7th PCRD that might provide additional financial support for the team, in the supervisory and control theme. DISC will provide 80 k Euros to IRISA in 2009.

·        Distribcom is involved in DOTS: Distributed, Open and Timed systems, an ANR Security Project. It might provide additional financial support for the team, in the timed and games aspect of the theme. DOTS will provide 33 k Euros to DISTRIBCOM in 2009.

·        Our partners in NUS has applied for a grant to support visits from the French and Indian teams.


3. Demande budgétaire




A. Coût global de la proposition (total des tableaux 1 et 2 : invitations, missions, ...)


B. Cofinancements utilisés (financements autres que Equipe Associée)


Financement "Équipe Associée" demandé (A.-B.)
(maximum 20 K€)




© INRIA - mise à jour le 17/10/2008