Distributed Unfolding of Petri Nets

Reference

Paolo Baldan, Stefan Haar, and Barbara König. Distributed unfolding of Petri nets. Technical Report CS-2006-1, Dipartimento di Informatica, Università Ca' Foscari di Venezia, 2006.

Abstract

Petri net unfoldings have been recognised as an efficient means to fight state space explosion when dealing with concurrent and distributed systems. Some recent Petri net-based approaches to fault diagnosis of distributed systems suggest to factor the problem into local diagnoses based on the unfoldings of local views of the system, which are then correlated with diagnoses from neighbouring supervisors. In this paper we propose a notion of system factorisation expressed in terms of pullback decomposition. To ensure coherence of the local views and completeness of the diagnosis, data exchange between the unfolders needs to be specified with care. We introduce interleaving structures as a format for data exchange between unfolders, and we propose a distributed algorithm for computing local views of the unfolding for each system component. The theory of interleaving structures is developed to prove correctness of the distributed unfolding algorithm.

Suggested BibTeX entry:

@techreport{BHK06b,
    author = {Paolo Baldan and Stefan Haar and Barbara K\"onig},
    institution = {Dipartimento di Informatica, Universit\`{a} Ca' Foscari di Venezia},
    number = {CS-2006-1},
    title = {Distributed Unfolding of {P}etri Nets},
    year = {2006}
}



PDF (302 kB)Conference version
© University of Duisburg-Essen, Theoretical Computer Science group