Skip to Main content Skip to Navigation
Reports

Trellis Processes : a Compact Representation for Runs of Concurrent Systems

Eric Fabre 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 : In the true concurrency semantics, runs of a concurrent system are represented as partial orders of events. To represent sets of such runs in a compact manner, traditional approaches rely on branching processes. The maximal branching process of a system, for the prefix relation, is known as the unfolding of that system. Unfoldings (of a finite complete prefix of them) are used for model-checking purposes, reachability analysis, system monitoring or diagnosis, etc. In particular, they enjoy nice factorization properties that allow the development of distributed/modular algorithms, for model checking or diagnosis. In this communication, we propose an alternate and somehow intermediate representation for runs of concurrent systems, where time is unfolded, but not the conflict relation. In few words, we abandon the requirement that no node of a branching process be in self-conflict, and allow confluence of conflicting histories. We obtain in that way trellis processes, and the time-unfolding of a system. The latter represents the same configuration set as the familiar unfolding, while being more compact in width. Moreover, trellis processes generalize to concurrent systems the usual notion of trellis of an automaton, which forms the support of most on-line monitoring algorithms. Through a suitable co-reflection of trellis nets in the category of safe nets, we finally prove that time-unfoldings enjoy the same factorization properties as standard unfoldings, which makes these more compact structures possible candidates for distributed verification/diagnosis algorithms.
Document type :
Reports
Complete list of metadata

https://hal.inria.fr/inria-00070452
Contributor : Rapport de Recherche Inria <>
Submitted on : Friday, May 19, 2006 - 8:31:54 PM
Last modification on : Thursday, January 7, 2021 - 4:28:50 PM
Long-term archiving on: : Sunday, April 4, 2010 - 9:15:15 PM

Identifiers

  • HAL Id : inria-00070452, version 1

Citation

Eric Fabre. Trellis Processes : a Compact Representation for Runs of Concurrent Systems. [Research Report] RR-5554, INRIA. 2005, pp.34. ⟨inria-00070452⟩

Share

Metrics

Record views

282

Files downloads

348