EDIS | Guide | FAQ | New | Search | Bibliography | Index | Feedback | About |
[EDIS Logo]

Encyclopedia of Delay-Insensitive Systems (EDIS)


The Encyclopedia of Delay-Insensitive Systems (EDIS) presents each type of system in a single system document comprising the following sections: These sections are discussed in more detail below (also see EDIS Internal Naming and Structuring Conventions).

Preliminary Remarks

System types

A system type is a parameterized family of systems. The terminal identifiers are always among the parameters, though they are usually left implicit in the system name. As an example consider the (type of all) mxn-Decision-Waits. It has as parameters: two positive integers m and n, m+n input terminals, and mn output terminals.

Substituting an appropriate value for each parameter yields a particular system, also called an instance of the system type. Partial substitution yields a subtype. For example, the mx2-Decision-Waits are a subtype of the mxn-Desicion-Waits. To obtain an instance of an mx2-Desicion-Wait, one should also substitute a value for m and indicate the terminal identifiers of the instance.

A statement such as `an mxn-Desicion-Wait is output deterministic' applies to the whole type, that is, to all mxn-Desicion-Wait instances.

System Names

Many systems are known by various names. The names used in EDIS were chosen with the following criteria in mind. Names are (preferably) But usually one cannot have it all (also see Miscellaneous).

In the document presenting system Foo, all occurrences of the name Foo appear emphasized (as illustrated in this sentence). From other documents, references to Foo are accompanied by a hyperlink to Foo's system document (as illustrated in this sentence, where the hyperlink points to the preceding sentence). In a sense, the names used in EDIS are dummies, since they could be systematically replaced without affecting the global structure.

To be elaborated: Names for generalizations; incorporating parameters in names (as in mxn-Decision-Wait).


Specifications of systems are given in several ways for two reasons. Currently, the choice of formalisms is heavily influenced by this editor's preferences. Also the order in which the formalisms appear is based on personal taste. The connection diagram and state graph are shown first, because they are visually oriented.


The informal specification describes both the external structure and the observable behavior of the system. The terminology is chosen to be uniform and fairly precise, without being pedantic. It is intended to give a quick impression of the system. For details you should turn to specifications expressed in one of the formalisms below.

Input, output, terminal, signal, port, handshake, 2-phase, 4-phase...

XDI Model

The XDI Model appears first because it has some (though limited) way of dealing with progress that is easily expressed in terms of state graphs (we would like to keep the state graph near the beginning of the document).

Many systems have various pictorial representations. Choosing a schematic diagram for a system raises similar problems as choosing a name. Here are some of the criteria we consider. Diagrams are (preferably)

Where possible, an alternate initial state is indicated by making use of Initialized Wires rather than using dots or blobs at the initialized component.

Example of schematic diagram and state graph:

Schematic diagram for an RGD Arbiter:

[Zoom| FIG]

XDI state graph for an RGD Arbiter:

[Zoom| FIG]
Specification in XDI model.
The Zoom link brings up a picture that is magnified by a factor two in both dimensions. The Fig link brings up the xfig source of the picture. The Specification in XDI model link bring up the description of the state graph in AND/IF format.


For specifications that also appear in the VERDECT library, we have used the same name as in that library. The given specifications can mostly be offered directly to VERDECT (using copy and paste). This may not be the case for some generalized specifications, which must first be properly instantiated.

We have aimed at fully parameterized definitions. That is, we write

define MERGE( a?, b?, c! ) =
       pref *[ (a? | b?); c! ]
rather than
define MERGE = pref *[ (a? | b?); c! ] end
Currently, VERDECT supports only parameterization over terminal identifiers. A VERDECT specification is stored in a separate file. When shorter than a certain limit it is also embedded in the system page.

DI Algebra

DI Algebra specifications are written in a format that is understood by the DIGG and Ludwig tools. DI Algebra, as it was originally proposed by Josephs and Udding, has a drawback when it comes to specifying components with separate environments. To overcome this, the notion of channels or alternations is introduced. Both DIGG and Ludwig accept a syntax that is extended with alternations.

A DI Algebra specification is stored in a separate file. When shorter than a certain limit it is also embedded in the system page.


We include both structural and behavioral properties. Concerning structure there is the number of input/output terminals. Behavioral properties include:

The analysis report generated by the XDI State Graph Tool is made available as xdi-report.html. More detailed information on what is in the report and how to read the report will appear here later.


DI Decompositions

Using Boolean Gates

Using Transistors


System type S is said to generalize system type T when T can be obtained from S by partial instantiation, that is, by substituting values for some of S's parameters.


Everything relevant that has no place elsewhere goes here. For instance, alternative names and connection diagrams, including references to the litarature. Historic footnotes. Controversies, difficulties, conjectures, and open problems.


Keys to cited literature are collected here for quick reference.

Last modified at Tue Nov 10 12:49:26 1998
Encyclopedia of Delay-Insensitive Systems
Copyright © 1995-1998 Tom Verhoeff / Tom.Verhoeff@acm.org