The behavior of shared objects: Concept, pitfalls, and a new model (Q1119023)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The behavior of shared objects: Concept, pitfalls, and a new model |
scientific article |
Statements
The behavior of shared objects: Concept, pitfalls, and a new model (English)
0 references
1989
0 references
The authors present a theoretical study of the behavior of overlapping concurrent operations on shared objects. Such objects can be found on all levels of a distributed system from hardware registers to files. The authors discuss the problem at the hardware level in order to stress the fundamental nature of the problem. Nevertheless, the considerations can be immediately applied to high-level operations. In the first part of the paper, the authors compare the behavior of different kinds of registers (safe, regular, atomic) and arbiters. They review the well-known results that safe registers are enough to build any other type of register under the assumption of bounded response time. There seems, however, to be a common agreement that an arbiter which is guaranteed to make a decision in bounded time cannot be built out of electronic components. Thus, it is necessary to study how to define semantics of concurrent operations under the assumption of unbounded response time. The authors take a first step in this direction and define a generalized finite state automaton. In contrary to conventional automata, the state transition is not assumed to be completed instantaneously, but at any time after the input is applied. Thus, it is possible that some operations overlap. The definition is illustrated by describing a flip-flop, a counter and an arbiter. The paper is well written; at the top of page 149, the second equal sign should be read as a plus sign.
0 references
probabilistic automata
0 references
specification
0 references
concurrency
0 references
asynchronous circuits
0 references
shared registers
0 references
arbiters
0 references
nonatomic operations
0 references
distributed systems
0 references