Designing systolic, distributed buffers with bounded response time

J.L.W. Kessels, M. Rem

Research output: Contribution to journalArticleAcademicpeer-review

3 Citations (Scopus)


Several buffer designs are derived by applying a design methodology that is based on so-called abstract states. Abstract states are euivalence classes of communication histories. These abstract states are very useful in the verification of program transformations, since they facilitate the definition of a function mapping the states of the transformed automaton onto the states of the original one. Three kinds of bufferes are discussed: the stack, the first-in first-out queue, and the priority queue. The designs are systolic and offer bounded response time, which means that all permissible communications are accepted within a time bounded by a constant. The design of the stack offers maximum storage utilization as well. We show that the properties of bounded response time and maximum storage utilization cannot be combined in distributed systolic queues.
Original languageEnglish
Pages (from-to)37-43
Number of pages7
JournalDistributed Computing
Issue number1
Publication statusPublished - 1990


Dive into the research topics of 'Designing systolic, distributed buffers with bounded response time'. Together they form a unique fingerprint.

Cite this