Communicating finite-state machine

Last updated

In computer science, a communicating finite-state machine is a finite state machine labeled with "receive" and "send" operations over some alphabet of channels. They were introduced by Brand and Zafiropulo, [1] and can be used as a model of concurrent processes like Petri nets. Communicating finite state machines are used frequently for modeling a communication protocol since they make it possible to detect major protocol design errors, including boundedness, deadlocks, and unspecified receptions. [2]

Contents

The advantage of communicating finite state machines is that they make it possible to decide many properties in communication protocols, beyond the level of just detecting such properties. This advantage rules out the need for human assistance or restriction in generality. [1]

Communicating finite state machines can be more powerful than finite state machines in situations where the propagation delay is not negligible (so that several messages can be in transit at one time) and in situations where it is natural to describe the protocol parties and the communication medium as separate entities. [1]

Communicating hierarchical state machine

Hierarchical state machines are finite state machines whose states themselves can be other machines. Since a communicating finite state machine is characterized by concurrency, the most notable trait in a communicating hierarchical state machine is the coexistence of hierarchy and concurrency. This has been considered highly suitable as it signifies stronger interaction inside the machine.

However, it was proved that the coexistence of hierarchy and concurrency intrinsically costs language inclusion, language equivalence, and all of universality. [3]

Definition

Protocol

For an arbitrary positive integer , a protocol [1] :3 with process(es) is a quadruple with:

Global state

A global state is a pair where

The initial global state is a pair where

Step

There are two kinds of steps, steps in which message are received and steps in which messages are sent.

A step in which the process receive a message previously sent by the -th process is a pair of the form when , with . Similarly, a pair in which a message is sent by the -th process to the -th one is a pair of the form when

Run

A run is a sequence of global states such that a step relate a state to the next one, and such that the first state is initial.

It is said that a global state is reachable if there exists a run passing through this state.

Problems

It has been proved with the introduction of the concept itself that when two finite state machines communicate with only one type of messages, boundedness, deadlocks, and unspecified reception state can be decided and identified while such is not the case when the machines communicate with two or more types of messages. Later, it has been further proved that when only one finite state machine communicates with single type of message while the communication of its partner is unconstrained, we can still decide and identify boundedness, deadlocks, and unspecified reception state. [2]

It has been further proved that when the message priority relation is empty, boundedness, deadlocks and unspecified reception state can be decided even under the condition in which there are two or more types of messages in the communication between finite state machines. [4]

Boundedness, deadlocks, and unspecified reception state are all decidable in polynomial time (which means that a particular problem can be solved in tractable, not infinite, amount of time) since the decision problems regarding them are nondeterministic logspace complete. [2]

Extensions

Some extensions considered are:

Channel system

A channel system is essentially a version of communicating finite-state machine in which the machine is not divided into distinct process. Thus, there is a single state of state, and there is no restriction relating which system can read/write on any channel.

Formally, given a protocol , its associated channel system is , where is the set of and of .

Related Research Articles

In computability theory, the Ackermann function, named after Wilhelm Ackermann, is one of the simplest and earliest-discovered examples of a total computable function that is not primitive recursive. All primitive recursive functions are total and computable, but the Ackermann function illustrates that not all total computable functions are primitive recursive.

<span class="mw-page-title-main">Inner product space</span> Generalization of the dot product; used to define Hilbert spaces

In mathematics, an inner product space is a real vector space or a complex vector space with an operation called an inner product. The inner product of two vectors in the space is a scalar, often denoted with angle brackets such as in . Inner products allow formal definitions of intuitive geometric notions, such as lengths, angles, and orthogonality of vectors. Inner product spaces generalize Euclidean vector spaces, in which the inner product is the dot product or scalar product of Cartesian coordinates. Inner product spaces of infinite dimension are widely used in functional analysis. Inner product spaces over the field of complex numbers are sometimes referred to as unitary spaces. The first usage of the concept of a vector space with an inner product is due to Giuseppe Peano, in 1898.

<span class="mw-page-title-main">Quantum teleportation</span> Physical phenomenon

Quantum teleportation is a technique for transferring quantum information from a sender at one location to a receiver some distance away. While teleportation is commonly portrayed in science fiction as a means to transfer physical objects from one location to the next, quantum teleportation only transfers quantum information. The sender does not have to know the particular quantum state being transferred. Moreover, the location of the recipient can be unknown, but to complete the quantum teleportation, classical information needs to be sent from sender to receiver. Because classical information needs to be sent, quantum teleportation cannot occur faster than the speed of light.

<span class="mw-page-title-main">Gram–Schmidt process</span> Orthonormalization of a set of vectors

In mathematics, particularly linear algebra and numerical analysis, the Gram–Schmidt process or Gram-Schmidt algorithm is a way of making two or more vectors perpendicular to each other.

In computer science, communicating sequential processes (CSP) 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, based on message passing via channels. CSP was highly influential in the design of the occam programming language and also influenced the design of programming languages such as Limbo, RaftLib, Erlang, Go, Crystal, and Clojure's core.async.

<span class="mw-page-title-main">Lattice model (physics)</span>

In mathematical physics, a lattice model is a mathematical model of a physical system that is defined on a lattice, as opposed to a continuum, such as the continuum of space or spacetime. Lattice models originally occurred in the context of condensed matter physics, where the atoms of a crystal automatically form a lattice. Currently, lattice models are quite popular in theoretical physics, for many reasons. Some models are exactly solvable, and thus offer insight into physics beyond what can be learned from perturbation theory. Lattice models are also ideal for study by the methods of computational physics, as the discretization of any continuum model automatically turns it into a lattice model. The exact solution to many of these models includes the presence of solitons. Techniques for solving these include the inverse scattering transform and the method of Lax pairs, the Yang–Baxter equation and quantum groups. The solution of these models has given insights into the nature of phase transitions, magnetization and scaling behaviour, as well as insights into the nature of quantum field theory. Physical lattice models frequently occur as an approximation to a continuum theory, either to give an ultraviolet cutoff to the theory to prevent divergences or to perform numerical computations. An example of a continuum theory that is widely studied by lattice models is the QCD lattice model, a discretization of quantum chromodynamics. However, digital physics considers nature fundamentally discrete at the Planck scale, which imposes upper limit to the density of information, aka Holographic principle. More generally, lattice gauge theory and lattice field theory are areas of study. Lattice models are also used to simulate the structure and dynamics of polymers.

<span class="mw-page-title-main">Correlation function (quantum field theory)</span> Expectation value of time-ordered quantum operators

In quantum field theory, correlation functions, often referred to as correlators or Green's functions, are vacuum expectation values of time-ordered products of field operators. They are a key object of study in quantum field theory where they can be used to calculate various observables such as S-matrix elements. They are closely related to correlation functions between random variables, although they are nonetheless different objects, being defined in Minkowski spacetime and on quantum operators.

In linear algebra, the Gram matrix of a set of vectors in an inner product space is the Hermitian matrix of inner products, whose entries are given by the inner product . If the vectors are the columns of matrix then the Gram matrix is in the general case that the vector coordinates are complex numbers, which simplifies to for the case that the vector coordinates are real numbers.

In mathematical economics, the Arrow–Debreu model is a theoretical general equilibrium model. It posits that under certain economic assumptions there must be a set of prices such that aggregate supplies will equal aggregate demands for every commodity in the economy.

The Stanford Research Institute Problem Solver, known by its acronym STRIPS, is an automated planner developed by Richard Fikes and Nils Nilsson in 1971 at SRI International. The same name was later used to refer to the formal language of the inputs to this planner. This language is the base for most of the languages for expressing automated planning problem instances in use today; such languages are commonly known as action languages. This article only describes the language, not the planner.

<span class="mw-page-title-main">LOCC</span> Method in quantum computation and communication

LOCC, or local operations and classical communication, is a method in quantum information theory where a local (product) operation is performed on part of the system, and where the result of that operation is "communicated" classically to another part where usually another local operation is performed conditioned on the information received.

Semidefinite programming (SDP) is a subfield of mathematical programming concerned with the optimization of a linear objective function over the intersection of the cone of positive semidefinite matrices with an affine space, i.e., a spectrahedron.

In the mathematical discipline of functional analysis, the concept of a compact operator on Hilbert space is an extension of the concept of a matrix acting on a finite-dimensional vector space; in Hilbert space, compact operators are precisely the closure of finite-rank operators in the topology induced by the operator norm. As such, results from matrix theory can sometimes be extended to compact operators using similar arguments. By contrast, the study of general operators on infinite-dimensional spaces often requires a genuinely different approach.

In arithmetic, a complex-base system is a positional numeral system whose radix is an imaginary or complex number.

In computer science, a computation is said to diverge if it does not terminate or terminates in an exceptional state. Otherwise it is said to converge. In domains where computations are expected to be infinite, such as process calculi, a computation is said to diverge if it fails to be productive.

The Harrow–Hassidim–Lloyd algorithm or HHL algorithm is a quantum algorithm for numerically solving a system of linear equations, designed by Aram Harrow, Avinatan Hassidim, and Seth Lloyd. The algorithm estimates the result of a scalar measurement on the solution vector to a given linear system of equations.

In mathematics, specifically group theory, a descendant tree is a hierarchical structure that visualizes parent-descendant relations between isomorphism classes of finite groups of prime power order , for a fixed prime number and varying integer exponents . Such groups are briefly called finitep-groups. The vertices of a descendant tree are isomorphism classes of finite p-groups.

In computer science, a channel system is a finite state machine similar to communicating finite-state machine in which there is a single system communicating with itself instead of many systems communicating with each other. A channel system is similar to a pushdown automaton where a queue is used instead of a stack. Those queues are called channels. Intuitively, each channel represents a sequence a message to be sent, and to be read in the order in which they are sent.

In computer science, a run of a sequence is a non-decreasing range of the sequence that cannot be extended. The number of runs of a sequence is the number of increasing subsequences of the sequence. This is a measure of presortedness, and in particular measures how many subsequences must be merged to sort a sequence.

The Korkine–Zolotarev (KZ) lattice basis reduction algorithm or Hermite–Korkine–Zolotarev (HKZ) algorithm is a lattice reduction algorithm.

References

  1. 1 2 3 4 D. Brand and P. Zafiropulo. On communicating finite-state machines. Journal of the ACM, 30(2):323–342, 1983.
  2. 1 2 3 Rosier, Louis E; Gouda, Mohamed G. Deciding Progress for a Class of Communicating Finite State Machines. Austin: University of Texas at Austin, 1983.
  3. Alur, Rajeev; Kannan, Sampath; Yannakakis, Mihalis. "Communicating hierarchical state machines," Automata, Languages and Programming. Prague: ICALP, 1999
  4. Gouda, Mohamed G; Rosier, Louis E. "Communicating finite state machines with priority channels," Automata, Languages and Programming. Antwerp: ICALP, 1984