Direction des Relations Internationales (DRI)
Programme INRIA "Equipes Associées"
(Demande
de prolongation)
I. DEFINITION
|
EQUIPE ASSOCIEE |
DST : Distributed systems,
Supervision and Time. |
|
sélection |
2009 |
|
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 & Algorithmique,
programmation, logiciels et architectures – Systèmes embarqués et temps réel. |
Pays : |
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 0226-0229 |
|
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 |
NOTA : Si la proposition
d'Equipe Associée comporte plusieurs partenaires, français et/ou étrangers,
vous pouvez :
- soit ajouter une colonne,
- soit dupliquer le tableau ci-dessus autant de fois que nécessaire, en
remplaçant "Coordinateur français ou étranger" par "Autre
participant français ou étranger".
La proposition en bref
|
Titre de la thématique de collaboration (en français et en anglais) : DST - Distributed systems : Supervision and Time |
|
Descriptif (environ 10 lignes) : 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. |
II. BILAN 2009
|
Changements majeurs survenus concernant l'Equipe Associée (modifications des objectifs scientifiques, des chercheurs impliqués) |
Rapport scientifique de l'année 2009
(joindre la page du programme de travail
initialement prévu fin 2008 pour l'année 2009
ou insérer un lien vers cette page)
Description de l'activité
scientifique de l'équipe associée et des résultats obtenus : publications, communications,
organisation de colloques, formation, soutenances de thèse, valorisation
économique, sociale, industrielle, enregistrement de logiciels, dépôt de
brevets ... (1 à 2 pages)
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. For a more detailed presentation of the objectives of the
associated team, we refer interested readers to the complete description at the
following address: http://www.irisa.fr/distribcom/DST09/DSTSoumission2009.html
Many fruitful discussions with our Indian and Singaporean partners took
place during the first year of the DST project. This led to define research
objectives on a smaller set of topics than in the original proposal, focusing
on the most promising techniques. These objectives involve two research themes
over distributed systems, namely time aspects, and supervision and control
aspects. Considering the later, the activities of DST in 2009 have mainly
focused on designing distributed controllers, and in particular making the
synthesis as small as possible. For the former, activities have focused on
network calculus, and on verification of timed MSCs.
Theme 1 : Supervision and control
This theme
addresses the problem of distributed
supervisory control, i.e. synthesis of a set of controllers supervising the
system in a distributed way, so that the monitored system satisfies some given
properties. The particular focus we choose is to minimize the resources needed
for the synthesis. For instance, we want to minimize the size of messages, the
overall number of messages, and the number of messages in transit at a given
time, such that the results we expect to find will be applicable in practice.
We did not produce publishable results yet, but we expect to publish some in
2010. We reviewed many different techniques to select the most promising ones: Wonham supervisory control theory [Wonham89], games of
imperfect information [Reif79] and Rabin’s Theorem to decide which global
configuration can be safely controlled. When the wining set of configurations
is known, game theory tells us that for safety objectives, a winning strategy
for the controllers is to ensure only that the current configuration is
winning. Then, one could use gossiping automata [Mulkun97] obtained with Zielonka theorem or Petri Net synthesis to obtain small
controllers staying in safe configurations.
Involved researchers :
Chennai
: M.Mukund,
Results in 2009:
·
Distributed Control of Concurrent Systems: Wonham
supervisory control theory for distributed systems is a big challenge due to
the partial information each process has on the global configuration of the system.
This added to the partial observation each process has already on its local
actions in Wonham control theory lead us to use the
results obtained for games of imperfect information. One member of DST studied
how to synthesize strategies in games with signals, leading to a publication in
the LICS conference [BGG09]. In these games, two players have partial and
incomparable information about the state of the system. They have antagonistic
goals. The aim is to extend these results to more than two players, with two
antagonist teams with conflicting goals, but where processes in the same team
collaborate. These games have been studied in full generality by [Reif79] but
strategy synthesis was shown undecidable. However, distributed games are not as
complicated as those studied in [Reif79]. This year, we discussed a particular
way of solving games, using Rabin’s Theorem. More precisely, there exists a
controller if and only if some logical fomula is
satisfied by the behavioural tree of the system. Two results seem promising:
first, Rabin’s theorem states that it is decidable whether an MSO formula is
satisfied by a regular tree. The second is that the behaviors
of distributed systems can be expressed
as a tree. The challenge is that one can define an MSO formula ensuring the
existence of a controller on a DAG (the unfolding of the system), or one can
define an MSO formula with subtree equivalence on the
tree structure. However, decidability of neither of these problems is yet
ensured.
·
Minimal implementation: This topic is a new problem
emerging from the discussions within DST, and addresses the minimal distributed implementation of a global
specification. It can be seen as a particular distributed supervision problem.
The main objective is to start from a global specification, and to distribute
it efficiently on a given architecture (i.e. synthesize a set of communicating
machines that preserves the global behaviour of the original specification). Of
course, this implementation cannot be a simple projection of the global
specification on each site of the architecture, and processes composing the
distributed system need some coordination to ensure that the original
specification is implemented. Usually, simple parallel composition of the
communicating machines obtained via projection of the global specification will
allow more behaviors than in the specification. A lot
of work has been devoted to finding exact
implementations of global specifications (see [Mukund97] for instance). Here,
the objective is to study how to implement a global specification on a given
architecture when the obtained communicating machines are allowed additional
coordination messages that are implementable by the architecture. A solution to
this problem proposed in [Genest05] is to implement a leader election protocol
among strongly connected components (one process synchronize all the processes
in its component), and to overflow messages between connected components. Our
goal is to obtain minimal implementation, i.e. using as
little messages and synchronization as possible among processes.
Study of this problem is still in its infancy, but we expect preliminary result
arriving next year, based on Petri net implementation techniques.
·
Scheduler ensuring minimal number of messages
in transit: Scheduling
can be considered as a weakened version of supervisory control, ensuring minimal number of messages in transit by activating
processes according to an adequate strategy. The activities around scheduling
this year have been a continuation of the former work initiated during the
CASDS associated team, focussing on producing distributed schedulers, while the
scheduler produced after the CASDS project was global [2].
Theme 2 : Time
The second theme addressed by the DST project is time in distributed
systems. We want to address time from two points of view. The first one is the
study of quantitative aspects, using techniques such as (Max,+) algebra and
network calculus, for which both Distribcom and NUS have strong competences.
The second aspect is to verify timed and
distributed models, modelled as Message Sequence Charts, a formalism common to
several members of Distribcom and of CMI used to describe telecommunication
protocols (for which the timing aspect is crucial). The challenge here is to
avoid considering every linearization of
the systems to fight the combinatorial explosion (which would lead to
inefficiency and worse to undecidability), while time may force the system to
follow problematic linearizations.
Involved researchers :
Chennai
:
Results in 2009:
·
Quantitative aspects using simulation : At the occasion of Gunjan Aggarwal’s internship in
the Distribcom team this summer, we have developed a simulator for Timed
Message Sequence Charts. This simulator takes as input Message Sequence Charts
annotated with time, resource consumption and probabilities, transforms the
annotated model into a timed, colored and stochastic
Petri net, and performs a simulation of this net. The flow of
the obtained nets depict the workflow attached to finite (but
arbitrarily long) requests arriving in a distributed system. The simulator
allows for the simulation of sessions containing up to 10 000 requests,
and provides information such as the mean throughput of the system, … It will
soon be integrated to the SOFAT Scenario toolbox.
·
Quantitative aspects with nework
calculus : During Rami Adhami's master internship,
we have studied networks with cyclic dependencies in the Network Calculus
framework. In a communication network, several flows circulate and can create
cyclic dependences (e.g. there is one flow from node i
to node j and one from node j to node i). Deciding
whether a given network is stable or not (i.e. at any time the amount of data
and the delay of data in the network is bounded by a constant) is an open and
difficult problem. Here, we were interested in the stable case and the aim was
to compute upper bounds on the maximum transmission delay for a given flow. A
first general method using fix-points techniques has been developed, but it
gives very loose bounds. A more precise analysis of simple networks (rings) has
then been initiated. A promising method is linear programming. The worst-case
delay can be computed as the limit of linear programs (with fast convergence),
and some methods are still in development to boil down that limit to a single
linear program.
·
Verification of time constraints for concurrent
models: This year,
we started investigating properties of Timed Message Sequence Charts, in
particular during the visit of S.Akshay at IRISA.
This extension proposed by members of DST [AMN07] adds time constraints to
Message Sequence Charts (MSCs). This new model also
brings several new challenges. For instance, checking time constraints on timed
MSCs is an undecidable problem in general, and the only known solution has been
to restrict the considered models to the class of regular MSC
languages, and to consider every linearization of the system, which
is both inefficient and very restrictive. The difficulty is to find a way to
verify time constraints over a regular set of representative linearizations,
even when the considered model is not regular. In the general case, unbounded
MSCs with generic constraints can be used to encode two counter machines,
leading to undecidability. We have started investigating some very natural
restriction of time constraints which would allow efficient
timed model checking, and work for a large class of infinite-state timed
systems. Namely, the restrictions we are considering are that the timing
constraints shall never force the
different processes to drift far away from each other, and the non-zenoness condition, stating that there exists a bound on
the number of events forced to be
executed in a small amount of time (the constraint can still be compatible with time drifting and non zeno
execuctions).
Bibliography:
[AMN07] S. Akshay, M. Mukund,
K. Narayan Kumar, Checking Coverage for
Infinite Collections of Timed Scenarios. CONCUR 2007, p 181-196, 2005.
[BGG09] N. Bertrand, B. Genest,
H. Gimbert. Qualitative Determinacy and Decidability of Stochastic Games with
Signals. LICS 2009, p 319-328, 2009.
[Genest05] B. Genest, On Implementation of Global Concurrent Systems with Local Asynchronous
Controllers. CONCUR 2005, p 443-45,
2005.
[Mukund97] M. Mukund, M. A. Sohoni, Keeping Track of the Latest Gossip in a Distributed System. Distributed Computing 10(3), p 137-148, 1997.
[Ramadge89] P.J. Ramadge,
W.M. Wonham, The control of discrete
event systems, proc. of the IEEE special issue on Dynamics of Discrete Events
Systems, 77(1), p 81-98, 1989.
[Reif79]
Gary L. Peterson, John H. Reif: Multiple-Person
Alternation FOCS 1979: 348-363, 1979.
Publications :
[1] T. Gazagnaire, B. Genest,
L. Hélouët, P. S. Thiagarajan,
S. Yang: Causal Message Sequence Charts.
Theoretical Computer Science 410(41): p
4094-4110, 2009
This publication is a journal version of a work
started during the CASDS associated team. It is a special issue of TCS (theoretical Computer Science) journal published at the
occasion of Mogens Nielsen’s 60’th birthday.
[2] P. Darondeau, B. Genest, P. S. Thiagarajan, S.
Yang: Quasi-Static Scheduling of Communicating Tasks,
to appear in Information and Computation.,
2009
This publication was selected from a paper accepted at
the CONCUR 2008 conference, work done during the CASDS associated team.
[3] Anne Bouillard, Linh T.X. Phan and Samarjit Chakraborty, Functional Modeling of
This work was initiated during the former
collaboration within the CASDS associated team.
Software:
A simulator for timed scenarios was developed by G. Aggarwal during her internship in
Rapport financier 2009
Avant de remplir les tableaux, consultez les règles au
paragraphe "Financement" de la page
d'accueil du programme.
The invitation line sums up the cost of
invitation of S. Akshay (CMI), the internship of G.Aggarwal (this internship was funded by the INRIA
internship program, DST only cover travel expenses). The cost of this
internship appears as line 1 of the second table. The second line of the second
table sums up the cost of missions to Chennai by P.Darondeau
and L.Hélouët in January 2009, which were charged to the CASDS associated team.
|
1. Dépenses EA (effectuées sur les crédits de l'Equipe Associée) |
Montant dépensé |
|
Invitations des partenaires |
1145,5 (+1000 expected) |
|
Missions INRIA |
3396,60 (+6000 expected) |
|
Total |
4542,1 (+7000 expected) |
Justifiez en quelques lignes l'utilisation des crédits et en particulier une utilisation partielle du budget alloué.
|
2. Dépenses externes (effectuées sur des financements hors EA) |
Montant dépensé |
|
|
Nom de l'organisme 1 (*):INRIA |
||
|
Invitations des partenaires |
1900 |
|
|
Missions INRIA vers le partenaire |
3608,32 |
|
|
Total |
5508,32 |
|
(*) Ajouter ou supprimer des lignes au tableau ci-dessus de façon à faire figurer tous les organismes ayant contribué au financement de l'équipe associée
|
Total des financements externes dépensés |
5508.32 |
|
Total des financements EA et externes dépensés |
10050,42 (+7000 expected) |
Bilan des échanges effectués en 2009
1. Chercheurs Seniors
The first exchange between
INRIA Rennes and Chennai (missions by P. Darondeau
and L. Hélouët) were funded by the associated team CASDS,
which ended in 2008. We plan two missions to
|
Nom |
statut (1) |
provenance |
destination |
objet (2) |
durée (3) |
Coût (si financement EA) |
Coût (si financement externe) |
|
Darondeau, Philippe |
DR |
Rennes |
Chennai |
Visit to Chennai
Mathematical Institute & Institute for Mathematical Sciences +
participation to an Indo-French Workshop on Jan 29-31 |
10 days |
|
1796.07 (EA CASDS – 2006-2008)) |
|
Hélouët, Loïc |
CR1 |
Rennes |
Chennai |
Visit to Chennai
Mathematical Institute & Institute for Mathematical Sciences +
participation to an Indo-French Workshop on Jan 29-31 |
10 days |
|
1812.25 (EA CASDS – 2006-2008) |
|
Genest, Blaise |
CR1 |
Rennes |
Singapore |
Meeting at NUS from 11/02 to
22/02+ partcipation to SINFRA 09 (French/singaporian Workshop) |
11 days |
3396,60 |
|
|
|
|
|
|
|
|
|
|
|
Genest, Blaise |
CR1 |
Rennes |
Singapore |
|
10 days |
3000 |
(to be confirmed) |
|
Hélouët, Loïc |
CR1 |
Rennes |
Singapore |
|
10 days |
3000 |
(to be confirmed) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Total des durées |
31 days (+ 20 planned
at the end of this year |
(1) DR / CR /
professeur
(2) colloque, thèse,
stage, visite....
(3) précisez l'unité (mois, semaine..)
2. Juniors
We have hired an intern
student, Mrs Gunjan Aggarwal,
to work on simulation of timed scenarios. This internship took place from May
11th to July 24th.
S.Akshay is
currently completing a co-supervised PhD between Chennai and Cachan (LSV). We invited him in
We have planned to receive the visit of Paul Soumya, a PhD student at IMSC before the end of the year.
|
Nom |
statut (1) |
provenance |
destination |
objet (2) |
durée (3) |
Coût (si financement EA) |
Coût (si financement externe) |
|
Aggarwal, Gunjan |
Internship |
Guwahati, India |
Rennes |
Internship, from 11/05
to 24/07, financed by the Internship campaign
of INRIA |
2,5 months |
|
1900 |
|
Aggarwal, Gunjan |
Internship |
Guwahati, India |
Rennes |
Travel expenses |
|
688,23 |
|
|
S. Akshay,
|
PhD |
Chennai, via |
|
Working meeting |
1 week |
457,27 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Paul Soumya |
PhD |
Chennai (IMSC) |
Rennes |
|
2 weeks |
1000 |
(to be confirmed) |
|
|
|
|
|
|
|
|
|
|
Total des durées |
2,6 months (+ 2 weeks planned) |
(1) post-doc / doctorant
/ stagiaire
(2) colloque, thèse, stage, visite....
(3) précisez l'unité (mois, semaine..)
III. PREVISIONS
2010
Programme de travail
The proposed work programme can be summarized as
follows:
·
Distributed Control of Concurrent Systems: the general case is complicated
since routing between processes is arbitrary. We will thus first consider some
restricted architecture of communication such as tree structures where the
communication is only possible between fathers and sons, but not between
siblings or descendant. This should allow us to use concurrent games which are
decidable.
·
Minimal Implementation: Now that the minimal
implementation is clearly posed, (i.e. find an optimal implementation, with
respect to the number of messages, and the number of messages in transit at any
time, etc) we are ready to propose algorithmic solutions for the problem. A
possible solution may come from Petri net implementation techniques.
·
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. Pursue work on bound estimation using the
network calculus and linear programming techniques.
·
Timed Scenarios: we will investigate the restrictions on time constraints
we came up with in order to verify a large class of communication protocols
with timing constraints.
Overall, our aim is to obtain results on open problems
which are in the same time effectively usable, and to have them implemented,
for instance in our tool SOFAT. Industrial applications could be found among
the usual telecommunication partners of the teams Distribcom and S4, Alcatel
Lucent and France Telecom. We are currently writing a European IP Proposal
called Univerself on self management, in which
distributed supervisory control techniques will be used.
Starting from 15 of January 2010, Blaise
Genest will be a researcher at UMI IPAL,
Programme d'échanges avec budget prévisionnel
1. Echanges
Décrivez les
échanges prévus dans les deux sens : invitations de chercheurs de votre
partenaire et missions INRIA vers votre partenaire ;
Précisez s'il s'agit
de chercheurs confirmés ou de juniors (stagiaires,
doctorants, post-doctorants) ;
Motivez, si
possible, les raisons scientifiques (travail
commun, workshop,..) et précisez la durée prévue ;
Indiquez les
étudiants impliqués dans la proposition. Donnez une estimation de leur nombre,
pour chaque partenaire, et précisez si des thèses en cotutelle sont prévues ;
Résumez ensuite ces informations dans les
tableaux 1 et 2 ci-dessous en faisant une estimation budgétaire :
Visits to Chennai/Singapore
We plan three visits from senior researchers involved
in the DST team, plus a visit of a PhD student (that should be hired before the
end of 2009 on a bourse de la region
|
1. ESTIMATION DES DÉPENSES EN MISSIONS INRIA VERS LE PARTENAIRE |
Nombre de personnes |
Coût estimé |
|
Chercheurs confirmés |
2 |
6000 |
|
Post-doctorants |
|
|
|
Doctorants |
1 |
2000 |
|
Stagiaires |
|
|
|
Autre (précisez) : |
|
|
|
Total |
2 |
8000 |
Visits of Researchers from Chennai/Singapore
We plan to invite a senior researcher from Chennai or
The intern we hired last year is too young to start a
PhD this year, and in our experience, it is hard to convince English speaking students to come for a
Master in
Moreover,
visits of seniors are a good occasion to present research topics of their
respective teams. IRISA seniors met Ajay Kattepur, a
Master student of
|
2. ESTIMATION DES DÉPENSES EN INVITATIONS DES PARTENAIRES |
Nombre de personnes |
Coût estimé |
|
Chercheurs confirmés |
1 |
3000 |
|
Post-doctorants |
|
|
|
Doctorants |
2 |
3000 |
|
Stagiaires |
1 |
2800 |
|
Autre (précisez) : |
|
|
|
Total |
3 |
8800 |
2. Cofinancement
Cette
coopération bénéficie-t-elle déjà d'un soutien financier de la part de l'INRIA,
de l'organisme étranger partenaire ou d'un organisme tiers (projet européen, NSF, ...) ?
Indiquez ces éléments et donnez les montants associés.
P.S. Thiagarajan has received a
30 000 S$ (approx. 15 000 euros) support from NUS
for all the duration of the collaboration.
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 2010.
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 2010.
A European IP project Univerself
will be soon submitted. If accepted, there would be huge mutual benefit with
the Supervision and Control part of DST.
3. Demande budgétaire
Indiquez,
dans le tableau ci-dessous, le coût global estimé de la proposition et le
budget demandé à
(maximum 20 K€ pour une prolongation en 2e année et 10 K€
pour une 3e année).
|
Commentaires |
Montant |
|
A. Coût global de la proposition (total des tableaux 1 et 2 : invitations, missions, ...) |
16800 |
|
B. Cofinancements utilisés (financements autres que Equipe Associée) |
2000 |
|
Financement "Équipe Associée" demandé
(A.-B.) |
14800 |
Remarques ou observations :
We have tried to meet the recommendations
of the COST during the 2008 evaluation of DST, and to involve more junior
researchers. This summer, we have hired an Indian intern (G. Aggarwal, 2,5months) . We also received the visit of S. Akshay (PhD at CMI), and a 2 weeks visit of Paul Soumya (PhD at IMSC) is also expected before the end of the
year.
© INRIA - mise à jour le 08/07/2009