HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

Factorization of Unfoldings for Distributed Tile Systems Part 2: General Case

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 : We consider large distributed discrete event systems, systems obtained by connecting a possibly large number of elementary components. By «large» we mean that the size of the system prevents its study at a global level. We propose instead a framework to analyse such systems by parts, taking advantage of their modular definition. The key is twofold. We first represent their runs in a true concurrency semantic, which already reduces the state explosion phenomenon¸: trajectories which only differ by the ordering of concurrent events are not distinguished. The convenient data structures to represent sets of trajectories in this semantic are called branching processes of the system, and their maximal representative corresponds to the unfolding of the system. The second idea lies in the following result¸: the unfolding of a modular system factorizes as the product of unfoldings of its components, which gives an even more compact representation of runs of a distributed system. Therefore one should rather perform all computations on this factorized form. We propose an algebraic setting to do so¸: computations take place in the category of «augmented branching processes,» and rely on two operations¸: projection and product. We illustrate this approach on a simple problem¸: find the minimal factorization for the unfolding of the global system, which amounts to determining, for each component, runs that remain possible once this component is inserted in the global system.
Document type :
Complete list of metadata

Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Tuesday, May 23, 2006 - 5:15:35 PM
Last modification on : Friday, February 4, 2022 - 3:15:37 AM
Long-term archiving on: : Sunday, April 4, 2010 - 10:10:31 PM


  • HAL Id : inria-00071402, version 1


Eric Fabre. Factorization of Unfoldings for Distributed Tile Systems Part 2: General Case. [Research Report] RR-5186, INRIA. 2004. ⟨inria-00071402⟩



Record views


Files downloads