Calculus of Broadcasting Systems
Encyclopedia
Calculus of Broadcasting Systems (CBS) is a CCS
-like calculus
where processes
speak one at a time and each is heard instantaneously by all others. Speech is autonomous, contention between speakers being resolved nondeterministically
, but hearing only happens when someone else speaks. Observationally meaningful laws differ from those of CCS. The handshake communication of CCS is changed to broadcast communication in CBS. This allows several additional features:
Calculus of Communicating Systems
The Calculus of Communicating Systems 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...
-like calculus
Process calculus
In computer science, the process calculi are a diverse family of related approaches for formally modelling concurrent systems. Process calculi provide a tool for the high-level description of interactions, communications, and synchronizations between a collection of independent agents or processes...
where processes
Process (computing)
In computing, a process is an instance of a computer program that is being executed. It contains the program code and its current activity. Depending on the operating system , a process may be made up of multiple threads of execution that execute instructions concurrently.A computer program is a...
speak one at a time and each is heard instantaneously by all others. Speech is autonomous, contention between speakers being resolved nondeterministically
Nondeterminism
Nondeterminism may refer to:* Nondeterministic programming * Nondeterministic algorithm * Non-deterministic Turing machine * Indeterminacy in computation * Indeterminism...
, but hearing only happens when someone else speaks. Observationally meaningful laws differ from those of CCS. The handshake communication of CCS is changed to broadcast communication in CBS. This allows several additional features:
- Priority, which attaches only to autonomous actions, is simply added to CBS in contrast to CCS, where such actions are the result of communication.
- A CBS simulator runs a process by returning a list of values it broadcasts. This permits a powerful combination, CBS with the host language. It yields several elegant algorithms. Only processes with a unique response to each input are needed in practice, so weak bisimulation is a congruence.
- CBS subsystems are interfaced by translators; by mapping messages to silence, these can restrict hearing and hide speech. Reversing a translator turns its scope inside out. This permits a new specification for a communication link – the environment of each user should behave like the other user.
See also
- Pi-calculusPi-calculusIn theoretical computer science, the π-calculus is a process calculus originally developed by Robin Milner, and David Walker as a continuation of work on the process calculus CCS...
- Calculus of communicating systemsCalculus of Communicating SystemsThe Calculus of Communicating Systems 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...
(CCS) - Communicating sequential processesCommunicating sequential processesIn computer science, Communicating Sequential Processes is a formal language for describing patterns of interaction in concurrent systems. It is a member of the family of mathematical theories of concurrency known as process algebras, or process calculi...
(CSP) - BisimulationBisimulationIn theoretical computer science a bisimulation is a binary relation between state transition systems, associating systems which behave in the same way in the sense that one system simulates the other and vice-versa....
- Alternating bit protocolAlternating bit protocolAlternating bit protocol is a simple network protocol operating at the data link layer that retransmits lost or corrupted messages.Messages are sent from transmitter A to receiver B. Assume that the channel from A to B is initialized and that there are no messages in transit. Each message from A...