Designing systolic, distributed buffers with bounded response time

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.