Abstract
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 equivalence captures notions like functional equivalence of logical switches, equivalence of channel implementations and level of fault tolerance of a network.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Bonchi, F., König, B., Montanari, U.: Saturated semantics for reactive systems. In: Proc. of LICS, pp. 69–80. IEEE, Los Alamitos (2006)
Cardelli, L., Gordon, A.: Mobile Ambients. Theor. Comp. Science 1(240), 177–213 (2000)
Cenciarelli, P., Talamo, I., Tiberi, A.: Ambient Graph Rewriting. Electronic Notes in Theoretical Computer Science 117, 335–351 (2005)
Cenciarelli, P., Tiberi, A.: Rational Unification in 28 Characters. Electronic Notes in Theoretical Computer Science 127(5), 3–20 (2005)
Cleaveland, R., Parrow, J., Steffen, B.: The concurrency workbench: A semantics-based tool for the verification of concurrent systems. ACM ToPLaS 15(1), 36–72 (1993)
Cormen, T., Leiserson, C., Rivest, R.: Introduction to algorithms. MIT Press, Cambridge (1990)
Corradini, A., Montanari, U., Rossi, F., Ehrig, H., Heckel, R., Löwe, M.: Algebraic Approaches to Graph Transformation I: Basic Concepts and Double Pushout Approach. In: Handbook of Graph Grammars and Computing by Graph Transformation, ch. 3, vol. 1
Degano, P., Montanari, U.: A model for distributed systems based on graph rewriting. Journal of the ACM 34, 411–449 (1987)
Ehrig, H., König, B.: Deriving Bisimulation Congruences in the DPO Approach to Graph Rewriting. In: Walukiewicz, I. (ed.) FOSSACS 2004. LNCS, vol. 2987, pp. 151–166. Springer, Heidelberg (2004)
Ferrari, G., Montanari, U., Tuosto, E.: A LTS semantics of ambients via graph synchronization with mobility. In: Restivo, A., Ronchi Della Rocca, S., Roversi, L. (eds.) ICTCS 2001. LNCS, vol. 2202. Springer, Heidelberg (2001)
Ferrari, G., Montanari, U., Tuosto, E.: Model Checking for Nominal Calculi. In: Sassone, V. (ed.) FOSSACS 2005. LNCS, vol. 3441, pp. 1–24. Springer, Heidelberg (2005)
Hirsch, D., Montanari, U.: Synchronized hyperedge replacement with name mobility: A graphical calculus for name mobility. In: Agha, G.A., De Cindio, F., Rozenberg, G. (eds.) APN 2001. LNCS, vol. 2001. Springer, Heidelberg (2001)
König, B., Montanari, U.: Observational equivalence for synchronized graph rewriting with mobility. In: Kobayashi, N., Pierce, B.C. (eds.) TACS 2001. LNCS, vol. 2215, pp. 145–164. Springer, Heidelberg (2001)
Lanese, I.: Synchronization Strategies for Global Computing Models. PhD thesis, Univ. of Pisa (2006)
Lanese, I., Montanari, U.: A graphical fusion calculus. In: Proc. of COMETA 2003 (2003)
Leifer, J.: Operational Congruences for Reactive Systems. PhD thesis, Univ. of Cambridge (UK) (2001)
Leifer, J., Milner, R.: Deriving Bisimulation Congruences for Reactive Systems. In: Palamidessi, C. (ed.) CONCUR 2000. LNCS, vol. 1877, pp. 243–258. Springer, Heidelberg (2000)
Milner, R.: Bigraphical Reactive Systems. In: Larsen, K.G., Nielsen, M. (eds.) CONCUR 2001. LNCS, vol. 2154. Springer, Heidelberg (2001)
Milner, R., Parrow, J., Walker, D.: A calculus of mobile processes. Information and Computation 100, 1–77 (1992)
Montanari, U., Buscemi, M.: A First Order Coalgebraic Model of π-Calculus Early Observational Equivalence. In: Brim, L., Jančar, P., Křetínský, M., Kucera, A. (eds.) CONCUR 2002. LNCS, vol. 2421, pp. 449–465. Springer, Heidelberg (2002)
Parrow, J., Victor, B.: The fusion calculus: Expressiveness and symmetry in mobile processes. In: Proc.of LICS. IEEE Computer Society Press, Los Alamitos (1998)
Riely, J., Hennessy, M.: Distributed Processes and Location Failures. Theoretical Computer Science 266, 693–735 (2001)
Turi, D., Plotkin, G.D.: Towards a mathematical operational semantics. In: Proc. of LICS. IEEE Computer Society Press, Los Alamitos (1997)
Warneke, B., Last, M., Liebowitz, B., Pister, K.S.J.: Smart dust: Communicating with a cubic-millimeter computer. IEEE Computer 34(1), 44–51 (2001)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Cenciarelli, P., Gorla, D., Tuosto, E. (2008). Network Applications of Graph Bisimulation. In: Ehrig, H., Heckel, R., Rozenberg, G., Taentzer, G. (eds) Graph Transformations. ICGT 2008. Lecture Notes in Computer Science, vol 5214. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-87405-8_10
Download citation
DOI: https://doi.org/10.1007/978-3-540-87405-8_10
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-87404-1
Online ISBN: 978-3-540-87405-8
eBook Packages: Computer ScienceComputer Science (R0)