Direction des Relations Internationales (DRI)
EQUIPE ASSOCIEE 
DST : Distributed systems,
Supervision and Time. 
sélection 
2009 
EquipeProjet 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 : SINGAPORE 
Pays : INDIA 

Coordinateur français 
Coordinateur étranger 
Coordinateur étranger 
Nom, prénom 
Hélouët, Loïc 
P.S. Thiagarajan 
Madhavan Mukund 
Grade/statut 
CR1 
Professor 
Professor 
Organisme d'appartenance 
INRIA Rennes, Bretagne Atlantique Equipe Distribcom 

Chennai Mathematical
Institute 
Adresse postale 
IRISA, Campus de Beaulieu, 35042 Rennes Cedex, France 
School of Computing 
Chennai Mathematical Institute 
URL 
http://www.irisa.fr/distribcom/Personal_Pages/helouet/newloic.html 
http://www.comp.nus.edu.sg/~thiagu/ 
http://www.cmi.ac.in/~madhavan/ 
Téléphone 
33 2 99 84 75 90 
+65 6874 7998 
+91 44 2747 02260229 
Télécopie 
33 2 99 84 71 71 

+91 44 2747 0225 
Courriel 
Loic.helouet@irisa.fr 
thiagu@comp.nus.edu.sg 
madhavan@cmi.ac.in 
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. 
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.
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 worstcase 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. Eventcount 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
timedautomata, and hence their analysis can lead to statespace 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
(filllevel 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 channelbounded. 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 scenariobased 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 Highlevel
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 crosstheme 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.
Bibliography:
[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: 181196
[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 : QuasiStatic Scheduling of Communicating
Tasks. CONCUR 2008, 310324, LNCS 5201.
[Leucker02]
B. Bollig, M. Leucker, P. Lucas, Extending Compositional Message Sequence
Graphs. LPAR 2002: 6885
[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
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 20062008 period. His research interests include true concurrency
models, scenarios, and distributed systems.
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),
Chennai
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),
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
·
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
INRIAChennai joint cooperation (INRIA leader Gérard Boudol, UR SophiaAntipolis).
·
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 20062008 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, 166180, LNCS 4703.
[DGTY08] Ph. Darondeau, B. Genest, P. S. Thiagarajan, S. Yang: QuasiStatic Scheduling of
Communicating Tasks. CONCUR 2008, 310324, LNCS 5201.
3. Impact
The three groups in Chennai,
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
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 Highlevel 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 scenariobased diagnosis to include timed
considerations.
·
Timed
extensions of true concurrency models: study new timed extensions to deal with
ignored messages in scenarios.
1. Echanges
For
year 2009, the following visits are planed:
Person / Dates 
Duration 
Travel 
Accomodation & subsistence 
Total 
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 
Total 

11200 
14000 
25200 Eur 
1. ESTIMATION DES DÉPENSES EN MISSIONS INRIA VERS LE PARTENAIRE 
Nombre de personnes 
Coût estimé 
Chercheurs confirmés 
2 
7200 
Postdoctorants 


Doctorants 


Stagiaires 


Autre (précisez) : 


Total 
2 
7200 
2. ESTIMATION DES DÉPENSES EN INVITATIONS DES PARTENAIRES 
Nombre de personnes 
Coût estimé 
Chercheurs confirmés 
4 
14400 
Postdoctorants 


Doctorants 


Stagiaires 
1 
3600 
Autre (précisez) : 


Total 
5 
18000 
2. Cofinancement
·
CMI
and IMS in Chennai have a FrenchIndian collaboration named TimedDiscoveri. 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
·
Both
S4 and Distribcom are involved in DISC: Distributed Supervisory Control of
Large Plants, an european
project of the 7^{th} 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
Commentaires 
Montant 
A. Coût global de la proposition (total des tableaux 1 et 2 : invitations, missions, ...) 
25200 
B. Cofinancements utilisés (financements autres que Equipe Associée) 
6400 
Financement
"Équipe Associée" demandé (A.B.) 
18800 
© INRIA  mise à jour le 17/10/2008