Hostname: page-component-78c5997874-fbnjt Total loading time: 0 Render date: 2024-11-09T22:05:33.894Z Has data issue: false hasContentIssue false
  • English
  • Français

Synchrony versus causality in distributed systems†

Published online by Cambridge University Press:  23 December 2014

KIRSTIN PETERS ,
JENS-WOLFHARD SCHICKE-UFFMANN ,
URSULA GOLTZ  and
UWE NESTMANN
KIRSTIN PETERS
Affiliation:
School of Electrical Engineering and Computer Science, TU Berlin, Germany Emails: [email protected], [email protected]
JENS-WOLFHARD SCHICKE-UFFMANN
Affiliation:
Institute for Programming and Reactive Systems, TU Braunschweig, Germany
URSULA GOLTZ
Affiliation:
Institute for Programming and Reactive Systems, TU Braunschweig, Germany
UWE NESTMANN
Affiliation:
School of Electrical Engineering and Computer Science, TU Berlin, Germany Emails: [email protected], [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

Given a synchronous system, we study the question whether – or, under which conditions – the behaviour of that system can be realized by a (non-trivially) distributed and hence asynchronous implementation. In this paper, we partially answer this question by examining the role of causality for the implementation of synchrony in two fundamental different formalisms of concurrency, Petri nets and the π-calculus. For both formalisms it turns out that each ‘good’ encoding of synchronous interactions using just asynchronous interactions introduces causal dependencies in the translation.

Type
Paper
Information
Mathematical Structures in Computer Science , Volume 26 , Special Issue 8: Special Issue: Express'11 , December 2016 , pp. 1459 - 1498
Copyright
Copyright © Cambridge University Press 2014 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

†

This work was supported by the DFG (German Research Foundation), grants NE-1505/2-1 and GO-671/6-1.

References

Badouel, É., Caillaud, B. and Darondeau, P. (2002) Distributing finite automata through petri net synthesis. Formal Aspects of Computing 13 447–470.Google Scholar
Boreale, M. and Sangiorgi, D. (1998) A fully abstract semantics for causality in the π-calculus. Acta Informatica 35 (5) 353–400.CrossRefGoogle Scholar
Boudol, G. (1992) Asynchrony and the π-calculus (note). INRIA Research Report RR-1702.Google Scholar
Busi, N. and Gorrieri, R. (1995) A Petri net semantics for π-calculus. In: Proceedings of the 6th International Conference on Concurrency Theory, Lecture Notes in Computer Science 962 145–159.Google Scholar
Carbone, M. and Maffeis, S. (2003) On the expressive power of polyadic synchronisation in π-calculus. Nordic Journal of Computing 10 1–29.Google Scholar
Degano, P. and Priami, C. (1999) Non-interleaving semantics for mobile processes. Theoretical Computer Science 216 (1) 237–270.CrossRefGoogle Scholar
Fournet, C. and Gonthier, G. (1996) The reflexive chemical abstract machine and the join-calculus. In: Proceedings of the 23rd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, 372–385.Google Scholar
van Glabbeek, R. J. (1993) The linear time - branching time spectrum II. In: Proceedings of the 4th International Conference on Concurrency Theory, 66–81.Google Scholar
van Glabbeek, R. J. and Goltz, U. (2001) Refinement of actions and equivalence notions for concurrent systems. Acta Informatica 37 (4/5) 229–327.Google Scholar
van Glabbeek, R. J., Goltz, U. and Schicke, J.-W. (2008) On synchronous and asynchronous interaction in distributed systems. Technical Report 2008-04, TU Braunschweig. Extended abstract in Proceedings of the 33rd international symposium on Mathematical Foundations of Computer Science, Lecture Notes in Computer Science 5162 16–35. (Available at http://arxiv.org/abs/0901.0048v1.)Google Scholar
van Glabbeek, R. J., Goltz, U. and Schicke-Uffmann, J.-W. (2012) On distributability of Petri nets (extended abstract). In: Proceedings of the 15th International Conference on Foundations of Software Science and Computation Structures, Lecture Notes in Computer Science 7213 331–345.CrossRefGoogle Scholar
Gorla, D. (2008) Comparing communication primitives via their relative expressive power. Information and Computation 206 (8) 931–952.Google Scholar
Gorla, D. (2010) Towards a unified approach to encodability and separation results for process calculi. Information and Computation 208 (9) 1031–1053.Google Scholar
Honda, K. (1992) Notes on soundness of a mapping from π-calculus to ν-calculus. With comments added in October 1993.Google Scholar
Honda, K. and Tokoro, M. (1991) An object calculus for asynchronous communication. Proceedings of the European Conference on Object-Oriented Programming, Lecture Notes in Computer Science 512 133–147.Google Scholar
Hopkins, R. P. (1991) Distributable nets. In: Advances in Petri Nets. Lecture Notes in Computer Science 524 161–187.Google Scholar
Milner, R. and Sangiorgi, D. (1992) Barbed bisimulation. In: Proceedings of the 19th International Colloquium on Automata, Languages and Programming, Lecture Notes in Computer Science 623 685–695.Google Scholar
Nestmann, U. (1998) On the expressive power of joint input. In: Proceedings of the Fifth International Workshop on Expressiveness in Concurrency, Electronic Notes in Theoretical Computer Science 16 145–152.CrossRefGoogle Scholar
Nestmann, U. (2000) What is a ‘Good’ encoding of guarded choice?. Information and Computation 156 (1–2) 287–319.CrossRefGoogle Scholar
Palamidessi, C. (2003) Comparing the expressive power of the synchronous and the asynchronous π-calculi. Mathematical Structures of Computer Science 13 (5) 685–719.Google Scholar
Parrow, J. (2008) Expressiveness of process algebras. Electronic Notes in Theoretical Computer Science 209 173–186.Google Scholar
Peters, K. (2012) Translational Expressiveness|Comparing Process Calculi using Encodings, Ph.D. thesis, TU Berlin. (Available at: http://nbn-resolving.de/urn:nbn:de:kobv:83-opus-37495)Google Scholar
Peters, K. and Nestmann, U. (2010) Breaking symmetries. Electronic Proceedings in Theoretical Computer Science 41 136–150.Google Scholar
Peters, K. and Nestmann, U. (2012) Is it a ‘Good’ encoding of mixed choice? In: Proceedings of the 15th International Conference on Foundations of Software Science and Computational Structures. Lecture Notes in Computer Science 7213 210–224.Google Scholar
Peters, K., Nestmann, U. and Goltz, U. (2013) On distributability in process calculi. In: Proceedings of the 22nd European conference on Programming Languages and Systems. Lecture Notes in Computer Science 310–329.CrossRefGoogle Scholar
Petri, C. A. (1977) Non-sequential processes. GMD-ISF Report 77.05, GMD.Google Scholar
Pratt, V. R. (1985) The pomset model of parallel processes: Unifying the temporal and the spatial. In: Seminar on Concurrency, Carnegie-Mellon University 180–196.Google Scholar
Priami, C. (1996) Enhanced Operational Semantics for Concurrency, Ph.D. thesis, Universita' di Pisa-Genova-Udine.Google Scholar
Reisig, W. (1984) Partial order semantics versus interleaving semantics for CSP-like languages and its impact on fairness. In: Proceedings of the 11th Colloquium on Automata, Languages and Programming 403–413.Google Scholar
Sangiorgi, D. and Walker, D. (2001) The π-Calculus: A Theory of Mobile Processes, Cambridge University Press, NY, USA.Google Scholar
Schicke, J.-W. (2008) Studienarbeit: Asynchronous Petri net classes. TU Braunschweig.Google Scholar
Schicke, J.-W. (2009) Diplomarbeit: Synchrony and asynchrony in Petri nets. TU Braunschweig.Google Scholar