Asynchronous flows: the technical condition of proper operation and its generalization, International Journal of Computer Research Volume 22, Number 4, pp. 435–445, 2015
Mathematical Subject Classification (2010): 94C10
Keywords and phrases: asynchronous flow, race-free, the technical condition of proper operation
The asynchronous circuits from electronics are modelled by the so-called asynchronous flows, i.e. Boolean functions Φ:{0,1}n→{0,1}n that iterate their coordinates Φi in arbitrary discrete time, independently on each other. As in this paper there is no bound on the duration of an iteration, we use the unbounded delay model of computation of the Boolean functions. The uncertainties related to the behavior of the circuits and their models are mainly generated by technology.
In the study of the asynchronous sequential circuits, the situation when multiple coordinates of the state can change at the same time in called a race. When the outcome of the race affects critically the run of the circuit, for example its final state, the race is called critical. To avoid the critical races that could occur, the Boolean function Φ is specified in general so that only one coordinate of the state can change; such a circuit (identified with its model) is called race-free and we also say that the Boolean function fulfills the technical condition of proper operation. We formalize in this framework the technical condition of proper operation and give its generalization, consisting in the situation when races exist, but they are not critical. Then the flow behaves like in the situation when the coordinates were computed at the same time.
