Encyclopedia of Delay-Insensitive Systems (EDIS)

Introduction

The Encyclopedia of Delay-Insensitive Systems (EDIS) provides information on a large number of delay-insensitive (DI) systems (or whatever you want to call them instead of systems: automata, circuits, components, elements, machines, modules, networks, processes, units, etc.). The information includes:

Specifications, both informal and in various formalisms (XDI Model, VERDECT, DI Algebra).
Properties, such as symmetries (structural and behavioral automorphisms), classifications (kind of choice or nondeterminism involved), independent environments, etc.
Implementations, DI decompositions, and gate and/or transistor designs where relevant
Generalizations
Miscellaneous, such as associated problems and conjectures, historic notes, etc.
References

The Guide explains in more detail how information in EDIS is organized.

Motivations for EDIS

In the field of DI systems, a lot of work has been done over a long period of time. This has generated a wealth of information, not all of which is easily accessible. Numerous results belong to the category of `folk knowledge', which everyone in the field believes to be generally known, although it may never have been published in the open literature. Many of such results are not all that difficult to reconstruct, but their sheer number calls for a considerable effort to `reinvent the wheel' over and over again.

Example: How do you construct an n-dimensional Decision-Wait out of 2-dimensional ones? How do you construct an RGD Arbiter from a Mutual-Exclusion Element?

Furthermore, taken altogether, the terminology that has resulted over the years is sometimes confusing, ambiguous, or even contradictory.

Example: What is the specification of a Sequencer, or a Join? What is the difference between a C-Element, a Rendezvous, and a Join? What is a port, or a channel?

When building a new tool or setting up a new theory concerned with DI systems, one is always looking for some good examples.

Example: How does my tool or theory handle the specification or verification of ...? It is for you to pick ...

EDIS aims to provide clear information on numerous DI systems, thereby anchoring the `folk knowledge' of the DI field. EDIS is not intended to pass judgment on either the systems being presented or the formalisms used for presenting them.

Additional benefits of EDIS can be expected in such areas as education, training, and patent applications. Last, but not least, putting together EDIS will present many challenges, reveal gaps in our knowledge, and create new research opportunities.

Scope of EDIS

What does the field of DI systems encompass? Certainly not the whole of Asynchronous Circuits, though EDIS might be of interest to the Asynchrounous community. At the risk of leaving out many related items of interest to others, we have restricted ourselves to the field of delay-insensitive systems. This is a proper subset of quasi-delay-insensitive or speed-independent systems. Such a restriction seemed necessary to make the project at all feasible. Furthermore, it seems a reasonable restriction since the field of DI systems is already quite large and sufficiently interesting by itself.

Sources for EDIS

Tom Verhoeff started `collecting DI systems' in 1984. Since then he has brought together many little tidbits of information. This collection has been his starting point for building EDIS in 1995. We hope to learn more from other people who are willing to contribute. Of course, we also harvested from the literature (see the Bibliography).

Restrictions of EDIS

It is in the nature of an encyclopedia that it leaves most questions unanswered. But EDIS serves its purpose if it helps you formulate interesting questions. It is also in the nature of an encyclopeadia that it presents a compromise biased in the direction of the editors' interests. You'll have to take that for granted. Of course, your suggestions are always welcome (see Feedback).

It is tempting to clear up a field by introducing yet more terminology. We have tried to avoid that. Some consistent basic terminology must, however, be chosen to act as a framework, for otherwise the encyclopedia would become rather incoherent. In other cases (i.e., for non-basic terminology), the choice is often rather arbitrary.

Acknowledgments

EDIS was conceived during Tom's visit to the MAVERIC Research Group through support from the Department of Computer Science at the University of Waterloo in Ontario, Canada.