Abstract
A specification technique, formally equivalent to finite-state machines, is offered as an alternative because it is inherently distributed and more comprehensible. When applied to modules whose complexity is dominated by control, the technique guides the analyst to an effective decomposition of complexity, encourages well-structured error handling, and offers an opportunity for parallel computation. When applied to distributed protocols, the technique provides a unique perspective and facilitates automatic detection of some classes of error. These applications are illustrated by a controller for a distributed telephone system and the full-duplex alternating-bit protocol for data communication. Several schemes are presented for executing the resulting specifications.
Keywords
Computer scienceFinite-state machineProtocol (science)ComputationState (computer science)Distributed computingCommunications protocolController (irrigation)Error detection and correctionDecompositionAbstract state machinesTheoretical computer scienceComputer engineeringAlgorithmComputer network
Affiliated Institutions
Related Publications
Automatic verification of finite-state concurrent systems using temporal logic specifications
We give an efficient procedure for verifying that a finite-state concurrent system meets a specification expressed in a (propositional, branching-time) temporal logic. Our algor...
On the Execution of Fuzzy Programs Using Finite-State Machines
An abstract model for the execution of fuzzy programs using finite-state machines is described, Different ways of executing fuzzy programs are investigated. It is shown that the...
Efficient Kernel Machines Using the Improved Fast Gauss Transform
The computation and memory required for kernel machines with N training samples is at least O(N 2). Such a complexity is significant even for moderate size problems and is prohi...
An Improved Spectral Graph Partitioning Algorithm for Mapping Parallel Computations
Efficient use of a distributed memory parallel computer requires that the computational load be balanced across processors in a way that minimizes interprocessor communication. ...
Quantum theory, the Church–Turing principle and the universal quantum computer
It is argued that underlying the Church–Turing hypothesis there is an implicit physical assertion. Here, this assertion is presented explicitly as a physical principle: ‘every f...
Publication Info
- Year
- 1985
- Type
- article
- Volume
- 7
- Issue
- 1
- Pages
- 10-36
- Citations
- 50
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
50
OpenAlex
Cite This
Pamela Zave
(1985).
A distributed alternative to finite-state-machine specifications.
ACM Transactions on Programming Languages and Systems
, 7
(1)
, 10-36.
https://doi.org/10.1145/2363.2365
Identifiers
- DOI
- 10.1145/2363.2365