The behavior of shared objects: Concept, pitfalls, and a new model (Q1119023)

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.