Asynchronous Signalling Processes

Rajit Manohar and Yoram Moses

A model of processes that interact via asynchronous wires carrying Boolean signals is presented. In this model, modules, called processes, can be made arbitrarily complex, can maintain local memory and can have an arbitrary number of inputs and outputs. A variety of circuit models can be represented by networks of signalling processes. It is shown that in a network of signalling processes consisting solely of single-ouput processes and forks, every module is an eventual C element. Consequently, the computational power of such a network is severely limited. This establishes that the celebrated C-element property of DI circuits follows solely from the fact that single output modules communicate over stable asynchronous wires. Conversely, it is shown that any Boolean function can be implemented using four-input/two-output processes where every process is either one gate (single output) or a pair of gates (two output).