Abstract
We study reduction congruence, the most widely used notion of equality for the asynchronous π-calculus with timers, and derive several alternative characterisations, one of them being a labelled asynchronous bisimilarity. These results are adapted to an asynchronous π-calculus with timers, locations and message failure. In addition we investigate the problem of how to distribute value-passing processes in a semantics-preserving way.
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
Abdulla, P.A., Jonsson, B.: Verifying programs with unreliable channels. Info. & Comp. 127(2), 91–101 (1996)
Amadio, R.M.: An asynchronous model of locality, failure, and process mobility. In: Garlan, D., Le Métayer, D. (eds.) COORDINATION 1997. LNCS, vol. 1282. Springer, Heidelberg (1997)
Amadio, R.M., Prasad, S.: Localities and failures. In: Thiagarajan, P.S. (ed.) FSTTCS 1994. LNCS, vol. 880. Springer, Heidelberg (1994)
Berger, M.: Towards Abstractions for Distributed Systems. PhD thesis, Imperial College, London (2002)
Berger, M., Honda, K.: The Two-Phase Commit Protocol in an Extended π-Calculus. In: Proc. EXPRESS 2000. ENTCS, vol. 39 (2000)
Berger, M., Honda, K., Yoshida, N.: Sequentiality and the π-calculus. In: Abramsky, S. (ed.) TLCA 2001. LNCS, vol. 2044, p. 29. Springer, Heidelberg (2001)
Berger, M., Honda, K., Yoshida, N.: Genericity and the π-Calculus. In: Gordon, A.D. (ed.) FOSSACS 2003. LNCS, vol. 2620, pp. 103–119. Springer, Heidelberg (2003)
Bergstra, J.A., Ponse, A., Smolka, S.A. (eds.): Handbook of Process Algebra. Elsevier, Amsterdam (2001)
Börger, E., Stärk, R.: Abstract State Machines: A Method for High-Level System Design and Analysis. Springer, Heidelberg (2003)
Carbone, M., Maffeis, S.: On the expressive power of polyadic synchronisation in π-calculus. In: Proc. EXPRESS 2002. ENTCS, vol. 68 (2002)
Cardelli, L., Gordon, A.: Mobile ambients. TCS 240 (2000)
Fournet, C., Gonthier, G.: A hierarchy of equivalences for asynchronous calculi. In: Larsen, K.G., Skyum, S., Winskel, G. (eds.) ICALP 1998. LNCS, vol. 1443, Springer, Heidelberg (1998)
Fournet, C., Gonthier, G., Lévy, J.-J., Maranget, L., Rémy, D.: A Calculus of Mobile Agents. In: Sassone, V., Montanari, U. (eds.) CONCUR 1996. LNCS, vol. 1119, Springer, Heidelberg (1996)
Hennessy, M.: Timed process algebras: a tutorial. Tech. Rep. CS 1993:02, University of Sussex, Computer Science Department (1993)
Honda, K.: Two bisimilarities in ν-calculus. Tech. Rep. 92-002, Keio University, Department of Computer Science (1992)
Honda, K., Tokoro, M.: On asynchronous communication semantics. In: Tokoro, M., Wegner, P., Nierstrasz, O. (eds.) ECOOP-WS 1991. LNCS, vol. 612, Springer, Heidelberg (1992)
Honda, K., Yoshida, N.: On reduction-based process semantics. TCS 151 (1995)
Honda, K., Yoshida, N.: A uniform type structure for secure information flow. In: POPL 2002, pp. 81–92. ACM Press, New York (2002)
Mills, D.: Time synchronization server. URL, http://www.eecis.udel.edu/~ntp/
Milner, R., Parrow, J., Walker, D.: A calculus of mobile processes, parts I and II. Info. & Comp. 100(1) (1992)
Milner, R., Sangiorgi, D.: Barbed bisimulation. In: Kuich, W. (ed.) ICALP 1992. LNCS, vol. 623, Springer, Heidelberg (1992)
Riely, J., Hennessy, M.: Distributed processes and location failures. TCS 226 (2001)
Sangiorgi, D., Walker, D.: The π-Calculus: a Theory of Mobile Processes. Cambridge University Press, Cambridge (2001)
Sewell, P.: Global/Local Subtyping and Capability Inference for a Distributed π-calculus. In: Fiat, A. (ed.) Dagstuhl Seminar 1996. LNCS, vol. 1442, Springer, Heidelberg (1998)
Wojciechowski, P.: Nomadic Pict: Language and Infrastructure Design for Mobile Computation. PhD thesis, University of Cambridge (2000)
Yoshida, N., Berger, M., Honda, K.: Strong Normalisation in the π-Calculus. In: Proc. LICS 2001, pp. 311–322. IEEE, Los Alamitos (2001); The full version to appear in Journal of Information and Computation
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Berger, M. (2004). Basic Theory of Reduction Congruence forTwo Timed Asynchronous π-Calculi. In: Gardner, P., Yoshida, N. (eds) CONCUR 2004 - Concurrency Theory. CONCUR 2004. Lecture Notes in Computer Science, vol 3170. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-28644-8_8
Download citation
DOI: https://doi.org/10.1007/978-3-540-28644-8_8
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-22940-7
Online ISBN: 978-3-540-28644-8
eBook Packages: Springer Book Archive