[go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

On the Expressive Power of Global and Local Priority in Process Calculi

  • Conference paper
CONCUR 2007 – Concurrency Theory (CONCUR 2007)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 4703))

Included in the following conference series:

  • 703 Accesses

Abstract

Priority is a frequently used feature of many computational systems. In this paper we study the expressiveness of two process algebras enriched with different priority mechanisms. In particular, we consider a finite (i.e. recursion-free) fragment of asynchronous CCS with global priority (FAP, for short) and Phillips’ CPG (CCS with local priority), and we contrast their expressive power with that of two non-prioritised calculi, namely the π-calculus and its broadcast-based version, called bπ. We prove, by means of leader-election-based separation results, that there exists no encoding of FAP into π-Calculus or CPG, under certain conditions. Moreover, we single out another problem in distributed computing, we call the last man standing problem (LMS for short), that better reveals the gap between the two prioritised calculi above and the two non prioritised ones, by proving that there exists no parallel-preserving encoding of the prioritised calculi into the non-prioritised calculi retaining any sincere (complete but partially correct, i.e., admitting divergence or premature termination) semantics.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Baeten, J.C.M., Bergstra, J.A., Klop, J.W.: Ready-trace semantics for concrete process algebra with the priority operator. Comput. J. 30(6), 498–506 (1987)

    MATH  MathSciNet  Google Scholar 

  2. Camilleri, J., Winskel, G.: Ccs with priority choice. Inf. Comput. 116(1), 26–37 (1995)

    Article  MATH  MathSciNet  Google Scholar 

  3. Cleaveland, R., Hennessy, M.: Priorities in process algebras. Inf. Comput. 87(1/2), 58–77 (1990)

    Article  MATH  MathSciNet  Google Scholar 

  4. Cleaveland, R., Lüttgen, G., Natarajan, V.: Priority in process algebra. In: Bergstra, J., Ponse, A., Smolka, S. (eds.) Handbook of Process Algebra, pp. 711–765. Elsevier, Amsterdam (2001)

    Chapter  Google Scholar 

  5. Phillips, I.: Ccs with priority guards. In: Larsen, K.G., Nielsen, M. (eds.) CONCUR 2001. LNCS, vol. 2154, pp. 305–320. Springer, Heidelberg (2001)

    Chapter  Google Scholar 

  6. Bernardo, M., Gorrieri, R.: Extended markovian process algebra. In: Sassone, V., Montanari, U. (eds.) CONCUR 1996. LNCS, vol. 1119, pp. 315–330. Springer, Heidelberg (1996)

    Google Scholar 

  7. Hermanns, H.: Interactive Markov Chains: The Quest for Quantified Quality. In: Hermanns, H. (ed.) Interactive Markov Chains. LNCS, vol. 2428, Springer, Heidelberg (2002)

    Google Scholar 

  8. Bravetti, M., Gorrieri, R.: The theory of interactive generalized semi-markov processes. Theor. Comput. Sci. 282(1), 5–32 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  9. Bernardo, M., Gorrieri, R.: A tutorial on empa: A theory of concurrent processes with nondeterminism, priorities, probabilities and time. Theor. Comput. Sci. 202(1-2), 1–54 (1998)

    Article  MATH  MathSciNet  Google Scholar 

  10. Baeten, J., Bergstra, J., Klop, J.: Syntax and defining equations for an interrupt mechanism in process algebra. Fundamenta Informaticae IX(2), 127–168 (1986)

    MathSciNet  Google Scholar 

  11. Milner, R.: A Calculus of Communication Systems. LNCS, vol. 92. Springer, Heidelberg (1980)

    Google Scholar 

  12. Milner, R., Parrow, J., Walker, D.: A calculus of mobile processes, i. Inf. Comput. 100(1), 1–40 (1992)

    Article  MATH  MathSciNet  Google Scholar 

  13. Milner, R., Parrow, J., Walker, D.: A calculus of mobile processes, ii. Inf. Comput. 100(1), 41–77 (1992)

    Article  MATH  MathSciNet  Google Scholar 

  14. Ene, C., Muntean, T.: Expressiveness of point-to-point versus broadcast communications. In: Ciobanu, G., Păun, G. (eds.) FCT 1999. LNCS, vol. 1684, pp. 258–268. Springer, Heidelberg (1999)

    Chapter  Google Scholar 

  15. Bougé, L.: On the existence of symmetric algorithms to find leaders in networks of communicating sequential processes. Acta Inf. 25(2), 179–201 (1988)

    Article  MATH  Google Scholar 

  16. Palamidessi, C.: Comparing the expressive power of the synchronous and asynchronous pi-calculi. Mathematical Structures in Computer Science 13(5), 685–719 (2003)

    Article  MathSciNet  Google Scholar 

  17. Phillips, I.: Ccs with priority guards. Available at http://wwwhomes.doc.ic.ac.uk/~iccp/papers/ccspgfullrevised.pdf

  18. Milner, R.: The polyadic pi-calculus: a tutorial. In: Bauer, F.L., Brauer, W., Schwichtenberg, H. (eds.) Logic and Algebra of Specification, pp. 203–246. Springer, Heidelberg (1993)

    Google Scholar 

  19. Milner, R.: Communicating and mobile systems: the π-calculus. Cambridge University Press, New York (1999)

    Google Scholar 

  20. Nestmann, U.: What is a “good” encoding of guarded choice? Inf. Comput. 156(1-2), 287–319 (2000)

    Article  MATH  MathSciNet  Google Scholar 

  21. Palamidessi, C., Herescu, O.M.: A randomized encoding of the pi-calculus with mixed choice. Theor. Comput. Sci. 335(2-3), 373–404 (2005)

    Article  MATH  MathSciNet  Google Scholar 

  22. Cardelli, L., Gordon, A.D.: Mobile ambients. In: Nivat, M. (ed.) ETAPS 1998 and FOSSACS 1998. LNCS, vol. 1378, pp. 140–155. Springer, Heidelberg (1998)

    Chapter  Google Scholar 

  23. Bravetti, M., Gorrieri, R., Lucchi, R., Zavattaro, G.: Quantitative information in the tuple space coordination model. Theor. Comput. Sci. 346(1), 28–57 (2005)

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Università di Bologna, Dipartimento di Scienze dell’Informazione Mura Anteo Zamboni 7, 40127 Bologna, Italy

    Cristian Versari, Nadia Busi & Roberto Gorrieri

Authors
  1. Cristian Versari
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Nadia Busi
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Roberto Gorrieri
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Luís Caires Vasco T. Vasconcelos

Rights and permissions

Reprints and permissions

Copyright information

© 2007 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Versari, C., Busi, N., Gorrieri, R. (2007). On the Expressive Power of Global and Local Priority in Process Calculi. In: Caires, L., Vasconcelos, V.T. (eds) CONCUR 2007 – Concurrency Theory. CONCUR 2007. Lecture Notes in Computer Science, vol 4703. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-74407-8_17

Download citation

  • DOI: https://doi.org/10.1007/978-3-540-74407-8_17

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-74406-1

  • Online ISBN: 978-3-540-74407-8

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation