Partial Order Techniques for Distributed Discrete Event Systems: why you can't avoid using them

Eric Fabre 1 Albert Benveniste 1
1 DISTRIBCOM - Distributed and Iterative Algorithms for the Management of Telecommunications Systems
IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires, Inria Rennes – Bretagne Atlantique
Abstract : Monitoring or diagnosis of large scale distributed Discrete Event Systems with asynchronous communication is a demanding task. Ensuring that the methods developed for Discrete Event Systems properly scale up to such systems is a challenge. In this paper we explain why the use of partial orders cannot be avoided in order to achieve this objective. To support this claim, we try to push classical techniques (parallel composition of automata and languages) to their limits. We focus on on-line techniques, where a key difficulty is the choice of proper data structures to represent the set of all runs of a distributed system. We discuss the use of previously known structures such as execution trees and unfoldings. We propose an alternative and more compact data structure called trellis. We study the apparatus needed to extend the use of these data structures to represent distributed executions. And we show how such data structures can be used in performing distributed monitoring and diagnosis. The techniques reported here were used in an industrial context for fault management and alarm correlation in telecommunications networks. This report served as a support for a plenary address that was given by the second author at WODES'2006.
Type de document :
[Research Report] RR-5916, INRIA. 2007, pp.38
Liste complète des métadonnées

Littérature citée [1 références]  Voir  Masquer  Télécharger
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 20 juin 2007 - 14:50:01
Dernière modification le : mercredi 16 mai 2018 - 11:23:02
Document(s) archivé(s) le : lundi 23 mai 2011 - 16:51:15


Fichiers produits par l'(les) auteur(s)


  • HAL Id : inria-00077535, version 2


Eric Fabre, Albert Benveniste. Partial Order Techniques for Distributed Discrete Event Systems: why you can't avoid using them. [Research Report] RR-5916, INRIA. 2007, pp.38. 〈inria-00077535v2〉



Consultations de la notice


Téléchargements de fichiers