Algebra of communicating processes

The algebra of communicating processes (ACP) is an algebraic approach to reasoning about concurrent systems. It is a member of the family of mathematical theories of concurrency known as process algebras or process calculi. ACP was initially developed by Jan Bergstra and Jan Willem Klop in 1982, as part of an effort to investigate the solutions of unguarded recursive equations. More so than the other seminal process calculi (CCS and CSP), the development of ACP focused on the algebra of processes, and sought to create an abstract, generalized axiomatic system for processes, and in fact the term process algebra was coined during the research that led to ACP. ACP is fundamentally an algebra, in the sense of universal algebra. This algebra is a way to describe systems in terms of algebraic process expressions that define compositions of other processes, or of certain primitive elements. ACP uses instantaneous, atomic actions () as its primitives. Some actions have special meaning, such as the action , which represents deadlock or stagnation, and the action , which represents a silent action (abstracted actions that have no specific identity). Actions can be combined to form processes using a variety of operators. These operators can be roughly categorized as providing a basic process algebra, concurrency, and communication. Choice and sequencing – the most fundamental of algebraic operators are the alternative operator (), which provides a choice between actions, and the sequencing operator (), which specifies an ordering on actions. So, for example, the process first chooses to perform either or , and then performs action . How the choice between and is made does not matter and is left unspecified. Note that alternative composition is commutative but sequential composition is not (because time flows forward). Concurrency – to allow the description of concurrency, ACP provides the merge and left-merge operators. The merge operator, , represents the parallel composition of two processes, the individual actions of which are interleaved.