Deterministic execution of synchronous programs in an asynchronous environment. A compositional necessary and sufficient condition

Dumitru Potop-Butucaru 1 Robert De Simone 2 Yves Sorel 1
1 AOSTE - Models and methods of analysis and optimization for systems with real-time and embedding constraints
CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Paris-Rocquencourt, COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : Synchronous reactive formalisms form an appealing programming model for embedded system and Systems-on-Chip (SoC) design. Deploying synchronous programs onto asynchronous distributed execution platforms is an important issue, and has been the topic of substantial research in the past. The point is that signal/event absence in a reaction cannot be taken as granted because of communication latencies. A simple solution consists in systematically sending signal absence notifications, but it is unduly expensive at run-time. Sufficient properties have been proposed defining subsets of synchronous programs where asynchronous evaluation is faithful to their original specification. In essence they aim at preserving stream computation {\em monotonicity}, in the original formulation of Kahn Network principles, or {\em confluence}, as coined by R. Milner. Some of these criteria may become quite involved. In the current paper we show a precise technical result: If equivalence between the synchronous and the asynchronous semantics is congruence with respect to parallel constructors, then the "good" criterion amounts to a single step "diamond closure" property, with independent behaviors converging to the union of their effects. It should be remembered here that the {\em local} individual behaviors of components may themselves contain simultaneous events, thereby allowing complex synchronous modeling on this lower layer.
Type de document :
Rapport
[Research Report] RR-6656, INRIA. 2008, pp.20
Liste complète des métadonnées

Littérature citée [16 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00322563
Contributeur : Dumitru Potop-Butucaru <>
Soumis le : jeudi 18 septembre 2008 - 10:10:12
Dernière modification le : mercredi 31 janvier 2018 - 10:24:04
Document(s) archivé(s) le : vendredi 4 juin 2010 - 11:32:32

Fichier

RR-6656.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00322563, version 1

Collections

Citation

Dumitru Potop-Butucaru, Robert De Simone, Yves Sorel. Deterministic execution of synchronous programs in an asynchronous environment. A compositional necessary and sufficient condition. [Research Report] RR-6656, INRIA. 2008, pp.20. 〈inria-00322563〉

Partager

Métriques

Consultations de la notice

288

Téléchargements de fichiers

130