World Library  
Flag as Inappropriate
Email this Article

Calculus of Communicating Systems

Article Id: WHEBN0000420372
Reproduction Date:

Title: Calculus of Communicating Systems  
Author: World Heritage Encyclopedia
Language: English
Subject: Process calculus, Π-calculus, Actor model and process calculi history, Subject-oriented business process management, Algebra of Communicating Processes
Collection:
Publisher: World Heritage Encyclopedia
Publication
Date:
 

Calculus of Communicating Systems

The Calculus of Communicating Systems (CCS) is a process calculus introduced by Robin Milner around 1980 and the title of a book describing the calculus. Its actions model indivisible communications between exactly two participants. The formal language includes primitives for describing parallel composition, choice between actions and scope restriction. CCS is useful for evaluating the qualitative correctness of properties of a system such as deadlock or livelock.[1]

According to Milner, "There is nothing canonical about the choice of the basic combinators, even though they were chosen with great attention to economy. What characterises our calculus is not the exact choice of combinators, but rather the choice of interpretation and of mathematical framework".

The expressions of the language are interpreted as a labelled transition system. Between these models, bisimilarity is used as a semantic equivalence.

Syntax

Given a set of action names, the set of CCS processes is defined by the following BNF grammar:

P ::= \emptyset\,\,\, | \,\,\,a.P_1\,\,\, | \,\,\,A\,\,\, | \,\,\,P_1+P_2\,\,\, | \,\,\,P_1|P_2\,\,\, | \,\,\,P_1[b/a]\,\,\, | \,\,\,P_1{\backslash}a\,\,\,

The parts of the syntax are, in the order given above

empty process
the empty process \emptyset is a valid CCS process
action
the process a.P_1 can perform an action a and continue as the process P_1
process identifier
write A \overset{\underset{\mathrm{def}}{}}{=} P_1 to use the identifier A to refer to the process P_1 (which may contain the identifier A itself, i.e., recursive definitions are allowed)
choice
the process P_1+P_2 can proceed either as the process P_1 or the process P_2
parallel composition
P_1|P_2 tells that processes P_1 and P_2 exist simultaneously
renaming
P_1[b/a] is the process P_1 with all actions named a renamed as b
restriction
P_1{\backslash}a is the process P_1 without action a

Related calculi and models

  • Communicating Sequential Processes (CSP), developed by Tony Hoare, is a language that arose at a similar time to CCS.
  • The pi-calculus, developed by Milner in the late 80's, provides mobility of communication links by allowing processes to communicate the names of communication channels themselves.
  • PEPA, developed by Jane Hillston introduces activity timing in terms of exponentially distributed rates and probabilistic choice, allowing performance metrics to be evaluated.

Some other languages based on CCS:

Models that have been used in the study of CCS-like systems:

References

  • Robin Milner: A Calculus of Communicating Systems, Springer Verlag, ISBN 0-387-10235-3. 1980.
  • Robin Milner, Communication and Concurrency, Prentice Hall, International Series in Computer Science, ISBN 0-13-115007-3. 1989
  1. ^ Herzog, Ulrich, ed. (May 2007). "Tackling Large State Spaces in Performance Modelling". Formal Methods for Performance Evaluation. Lecture Notes in Computer Science 4486. Springer. pp. 318–370.  
This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
 
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
 
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.
 


Copyright © World Library Foundation. All rights reserved. eBooks from Project Gutenberg are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.