Paper Info
Title
Partial Order Techniques for Distributed Discrete Event Systems: Why You Cannot Avoid Using Them
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 and we eventually discover that partial order models arise at some point. 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, in a modular way. We discuss the use of previously known structures such as execution trees and unfoldings. We propose a novel and more compact data structure called "trellis." Then, we show how all the above 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 paper is an extended and improved version of the plenary address that was given by the second author at WODES' 2006.
Year
DOI
Venue
2007
10.1007/s10626-007-0016-1
Discrete Event Dynamic Systems
Keywords
Field
DocType
Discrete event systems,Distributed systems,Diagnosis,Partial orders,Unfoldings,Fault management,Alarm correlation
Asynchronous communication,Data structure,Telecommunications network,Computer science,Discrete event dynamic system,Automaton,Alarm correlation,Theoretical computer science,Fault management,Modular design,Distributed computing
Journal
Volume
Issue
ISSN
17
3
0924-6703
ISBN
Citations 
PageRank 
1-4244-0053-8
14
0.72
References 
Authors
33
2
Name
Order
Citations
PageRank
Eric Fabre1708.91
Albert Benveniste22831299.20