Skip to Main content Skip to Navigation

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. \\Ce document explique pourquoi l'on ne peut échapper au recours aux modèles d'ordres partiels pour l'algorithmique des systèmes à événements discrets répartis. Dans le présent document nous nous en tenons à la surveillance et ne traitons pas du contrôle. Les techniques présentées ont été utilisées dans un contexte industriel, pour la gestion répartie d'alarmes dans les réseaux de télécommunications.
Complete list of metadata

Cited literature [31 references]  Display  Hide  Download
Contributor : Anne Jaigu <>
Submitted on : Tuesday, May 16, 2006 - 8:45:48 AM
Last modification on : Thursday, January 7, 2021 - 4:17:35 PM
Long-term archiving on: : Monday, September 20, 2010 - 1:53:36 PM


  • HAL Id : inria-00068387, version 2


Eric Fabre, Albert Benveniste. Partial Order Techniques for Distributed Discrete Event Systems: why you can't avoid using them. [Research Report] PI 1800, 2006, pp.32. ⟨inria-00068387v2⟩



Record views


Files downloads