CNRS Verimag Laboratory

Grenoble, France

CNRS Verimag Laboratory

Grenoble, France
Time filter
Source Type

Donze A.,CNRS Verimag Laboratory | Fanchon E.,CNRS Complex Medical Engineering Laboratory | Gattepaille L.M.,CNRS Complex Medical Engineering Laboratory | Gattepaille L.M.,Uppsala University | And 2 more authors.
PLoS ONE | Year: 2011

Characterizing the behavior and robustness of enzymatic networks with numerous variables and unknown parameter values is a major challenge in biology, especially when some enzymes have counter-intuitive properties or switch-like behavior between activation and inhibition. In this paper, we propose new methodological and tool-supported contributions, based on the intuitive formalism of temporal logic, to express in a rigorous manner arbitrarily complex dynamical properties. Our multi-step analysis allows efficient sampling of the parameter space in order to define feasible regions in which the model exhibits imposed or experimentally observed behaviors. In a first step, an algorithmic methodology involving sensitivity analysis is conducted to determine bifurcation thresholds for a limited number of model parameters or initial conditions. In a second step, this boundary detection is supplemented by a global robustness analysis, based on quasi-Monte Carlo approach that takes into account all model parameters. We apply this method to a well-documented enzymatic reaction network describing collagen proteolysis by matrix metalloproteinase MMP2 and membrane type 1 metalloproteinase (MT1-MMP) in the presence of tissue inhibitor of metalloproteinase TIMP2. For this model, our method provides an extended analysis and quantification of network robustness toward paradoxical TIMP2 switching activity between activation or inhibition of MMP2 production. Further implication of our approach is illustrated by demonstrating and analyzing the possible existence of oscillatory behaviors when considering an extended open configuration of the enzymatic network. Notably, we construct bifurcation diagrams that specify key parameters values controlling the co-existence of stable steady and non-steady oscillatory proteolytic dynamics. © 2011 Donzé et al.

Devismes S.,CNRS Verimag Laboratory | Petit F.,University of Lyon | Tixeuil S.,University Pierre and Marie Curie
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) | Year: 2010

We consider a team of k identical, oblivious, semi-synchronous mobile robots that are able to sense (i.e., view) their environment, yet are unable to communicate, and evolve on a constrained path. Previous results in this weak scenario show that initial symmetry yields high lower bounds when problems are to be solved by deterministic robots. In this paper, we initiate research on probabilistic bounds and solutions in this context, and focus on the exploration problem of anonymous unoriented rings of any size. It is known that Θ(log n) robots are necessary and sufficient to solve the problem with k deterministic robots, provided that k and n are coprime. By contrast, we show that four identical probabilistic robots are necessary and sufficient to solve the same problem, also removing the coprime constraint. Our positive results are constructive. © 2010 Springer.

Bonakdarpour B.,University of Waterloo | Bozga M.,CNRS Verimag Laboratory | Jaber M.,CNRS Verimag Laboratory | Quilbeuf J.,CNRS Verimag Laboratory | Sifakis J.,CNRS Verimag Laboratory
Distributed Computing | Year: 2012

Although distributed systems are widely used nowadays, their implementation and deployment are still time-consuming, error-prone, and hardly predictable tasks. In this paper, we propose a method for producing automatically efficient and correct-by-construction distributed implementations from a model of the application software in Behavior, Interaction, Priority (BIP). BIP is a wellfounded component-based framework encompassing highlevel multi-party interactions for synchronizing components (e.g., rendezvous and broadcast) and dynamic priorities for scheduling between interactions. Our method transforms an arbitrary BIP model into a Send/Receive BIP model that is directly implementable on distributed execution platforms. The transformation consists in (1) breaking the atomicity of actions in components by replacing synchronous multiparty interactions with asynchronous Send/Receive interactions; (2) inserting distributed controllers that coordinate the execution of interactions according to a user-defined partition of interactions, and (3) adding a distributed algorithm for handling conflicts between controllers. The obtained Send/Receive BIP model is proven observationally equivalent to its corresponding initial model. Hence, all functional properties of the initial BIP model are preserved by construction in the implementation. Moreover, the obtained Send/Receive BIP model can be used to automatically derive distributed executable code. The proposed method is fully implemented. Currently, it is possible to generate C++ implementations for (1) TCP sockets for conventional distributed communication, (2) MPI for multi-processor platforms, and (3) POSIX threads for deployment on multi-core platforms. We present four case studies and report experimental results for different design choices including partition of interactions and choice of algorithm for distributed conflict resolution. © Springer-Verlag 2012.

Devismes S.,CNRS Verimag Laboratory
Proceedings of the 3rd International ACM Workshop on Reliability, Availability, and Security, WRAS 2010 | Year: 2010

In [4], the authors look at probabilistic bounds and solutions for the exploration of anonymous unoriented rings of any size by a cohort of robots. Considering identical, oblivious, and probabilistic robots, they show that at least four of them are necessary to solve the problem. Moreover, they give a randomized protocol for four robots working in any ring of size more than eight. Here we close the question of optimal (w.r.t. the cohort size) ring exploration by probabilistic robots. Indeed, we propose a protocol for four robots working in any ring of size less or equal to eight. Composing this protocol with the one in [4], we obtain a protocol for any ring-size.

Devismes S.,CNRS Verimag Laboratory | Petit F.,CNRS Laboratory for Informatics
ACM International Conference Proceeding Series | Year: 2012

In this paper, we address the unison problem. We consider the selfstabilizing algorithm proposed by Boulinier et al. We exhibit a bound on the step complexity of its stabilization time. In more details, the stabilization time of this algorithm is at most 2Dn3+(α+ 1)n2 +(α-2D)n steps, where n is the number of processes, D is the diameter of the network, and αis a parameter of the algorithm. Copyright © 2012 by the Association for Computing Machinery,Inc.

Legay A.,French Institute for Research in Computer Science and Automation | Delahaye B.,French Institute for Research in Computer Science and Automation | Bensalem S.,CNRS Verimag Laboratory
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) | Year: 2010

Quantitative properties of stochastic systems are usually specified in logics that allow one to compare the measure of executions satisfying certain temporal properties with thresholds. The model checking problem for stochastic systems with respect to such logics is typically solved by a numerical approach [31,8,35,22,21,5] that iteratively computes (or approximates) the exact measure of paths satisfying relevant subformulas; the algorithms themselves depend on the class of systems being analyzed as well as the logic used for specifying the properties. Another approach to solve the model checking problem is to simulate the system for finitely many executions, and use hypothesis testing to infer whether the samples provide a statistical evidence for the satisfaction or violation of the specification. In this tutorial, we survey the statistical approach, and outline its main advantages in terms of efficiency, uniformity, and simplicity. © 2010 Springer-Verlag.

Donze A.,CNRS Verimag Laboratory
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) | Year: 2010

We describe Breach, a Matlab/C++ toolbox providing a coherent set of simulation-based techniques aimed at the analysis of deterministic models of hybrid dynamical systems. The primary feature of Breach is to facilitate the computation and the property investigation of large sets of trajectories. It relies on an efficient numerical solver of ordinary differential equations that can also provide information about sensitivity with respect to parameters variation. The latter is used to perform approximate reachability analysis and parameter synthesis. A major novel feature is the robust monitoring of metric interval temporal logic (MITL) formulas. The application domain of Breach ranges from embedded systems design to the analysis of complex non-linear models from systems biology. © 2010 Springer-Verlag.

Heurtefeux K.,CNRS Verimag Laboratory | Valois F.,University of Lyon
Proceedings - International Conference on Advanced Information Networking and Applications, AINA | Year: 2012

Numerous localization protocols in Wireless Sensor Networks are based on Received Signal Strength Indicator. Because absolute positioning is not always available, localization based on RSSI is popular. More, no extra hardware is needed unlike solutions based on infra-red or ultrasonic. Moreover, the theory gives a RSSI as a function of distance. However, using RSSI as a distance metric involves errors in the measured values, resulting path-loss, fading, and shadowing effects. We present experimentation results from three large WSNs, each with up to 250 nodes. Based on our findings from the 3 systems, the relation between RSSI and distance is investigated according to the topology properties and the radio environment. We underline the intrinsic limitations of RSSI as a distance metric, in terms of accuracy and stability. Contrary to what we assumed, collaborative localization protocol based on Spring-Relaxation algorithm can not smooth the distance-estimation errors obtained with RSSI measurements. © 2012 IEEE.

Bozga M.,CNRS Verimag Laboratory | Jaber M.,CNRS Verimag Laboratory | Sifakis J.,CNRS Verimag Laboratory
IEEE Transactions on Industrial Informatics | Year: 2010

Behavior, Interaction, Priorities (BIP) is a component framework for constructing systems from a set of atomic components by using two kinds of composition operators: interactions and priorities. In this paper, we present a method that transforms the interactions of a component-based program in BIP and generates a functionally equivalent program. The method is based on the successive application of three types of source-to-source transformations: flattening of components, flattening of connectors, and composition of atomic components. We show that the system of the transformations is confluent and terminates. By exhaustive application of the transformations, any BIP component can be transformed into an equivalent monolithic component. From this component, efficient standalone C++ code can be generated. The method combines advantages of component-based description such as clarity, incremental construction, and reasoning with the possibility to generate efficient monolithic code. It has been integrated in the design methodology for BIP and it has been successfully applied to two non trivial examples described in this paper. © 2010 IEEE.

Bozga M.,CNRS Verimag Laboratory | Jaber M.,CNRS Verimag Laboratory | Maris N.,CNRS Verimag Laboratory | Sifakis J.,CNRS Verimag Laboratory
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) | Year: 2012

Dynamic architectures in which interactions between components can evolve during execution, are essential for modern computing systems such as web-based systems, reconfigurable middleware, wireless sensor networks and fault-tolerant systems. Currently, we lack rigorous frameworks for their modeling, development and implementation. We propose Dy-BIP a dynamic extension of the BIP component framework rooted in rigorous operational semantics and supporting a powerful and high-level set of primitives for describing dynamic interactions. These are expressed as symbolic constraints offered by interacting components and computed efficiently by an execution Engine. We present experimental results which validate the effectiveness of Dy-BIP and show significant advantages over using static architecture models. © 2012 Springer-Verlag.

Loading CNRS Verimag Laboratory collaborators
Loading CNRS Verimag Laboratory collaborators