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. Joep L.W. Kessels received an M.Sc. (Honors) degree in electrical engineering from the Eindhoven University of Technology, The Netherlands, in 1967. In 1969 he joined the Philips Research Laboratories in Eindhoven, where he has been involved in three major projects in the following research areas: applicative programming, distributed processing, and local area networks. Currently, he is engaged in the formal derivation of VLSI designs. His main research interests are design methodology and distributed processing. Martin Rem obtained an M.Sc. degree in mathematics at the University of Amsterdam in 1971 and a Ph.D. degree in computing science at the Eindhoven University of Technology in 1976. He is currently professor of mathematics and computing science at Eindhoven and part-time visiting professor at California Institute of Technology. Professor Rem is consultant for Philips Research and editor of Science of Computer Programming and Integration.