On the realizability and synthesis of delay-insensitive behaviors

This paper presents six properties, each of which, if satisfied by all the basic circuit elements used in synthesis, will also be satisfied by any delay-insensitive (DI) behavior realized by those circuit elements. Six relevant theorems are proved. The DI behaviors of classical circuit elements (e.g., AND, OR, inverter, merge, etc.) are then examined. It is found that they all satisfy the so called unique successor set (USS) property. As a result, it is proved that any DI behavior realized by a network of classical circuit elements necessarily exhibits the USS property. Some new circuit elements are needed to realize arbitrary DI behaviors (e.g., those that do not exhibit the USS property). A set of circuit elements is proposed. It is shown that these circuit elements are sufficient to implement any determinate finite state DI system