Network Applications of Graph Bisimulation

Pietro Cenciarelli, Daniele Gorla and Emilio Tuosto

Paper appeared in the 4th International Conference on Graph Transformation (ICGT 2008), Leicester (UK), September 7 - 13 2008


Synchronising Graphs is a system of parallel graph transformation designed for modeling process interaction in a network environment. We propose a theory of context-free synchronising graphs and a novel notion of bisimulation equivalence which is shown to be a congruence with respect to graph composition and node restriction. We use this notion of equivalence to study some sample network applications, and show that our bisimulation captures precisely notions like functional equivalence of logical switches, equivalence of channel implementations and level of fault tolerance of a network.

  author    =   {P. Cenciarelli, D. Gorla and E. Tuosto},
  title     =   {Network Applications of Graph Bisimulation},
  editor    =   {R. Heckel and G. Taentzer},
  booktitle =   {Proceedings of the 4th International Conference on Graph Transformation (ICGT'08)},
  series    =   {LNCS},
  volume    =  	{5214},
  pages     =  	{131--146},
  year      =  	{2008},
  publisher =   {Springer},

Home page / Publications