2

INTRODUCTION

what the system does, how messages move, and what are the protocols the computers use to

coordinate message reception and transmission in a network. This area has received considerable

attention both in the computer science and communications theory areas. It is characterized by a

lack of suitable models that can be used conveniently to describe complex systems and, at the same

time, not lose the essential aspects of detailed behavior. If one attempts to model all the details,

one quickly gets a description of even small systems which is too complex to "understand." On the

other hand, if one builds too simplified a model it is always suspect. Maybe one of the details that

has been left out might be critical to the working of the system. The third paper, by R. P.

Kurshan, describes a model that, in practice, has been found to be useful in the specification of

complex systems without any undetected loss of precision. Although the example considered in

this paper is not a "practical" problem, it illustrates some of the difficulties encountered in practice.

One of the questions that arises in the area of computer communications is: what is the

difference between computation and communication? Recently, computers have been realized

using "chips," devices consisting of interconnected transistors. With very large scale integration, it

is possible to have thousands of transistors on a single chip. One of the interesting theoretical

questions is how much area is required to do a specific computation using transistors and

interconnected wires laid out on a planar chip surface. However, there are tradeoffs between the

chip area and the time required for completing the computation. One combined complexity

measure is the product of the area and the square of the computing time. It turns out that one can

derive the lower bounds for this complexity measure. Surprisingly, these bounds are proved by

accounting just for the work necessary to communicate intermediate results between the various

switching elements which are the basic building blocks used on a chip. This is the subject of the

paper by T. Lengauer.

Professor Harrison was kind enough to lecture to us on diffusion approximation, a technique

used to investigate the behavior of computer communications systems under extreme congestion.

In the paper by Christopher Flores, we find an excellent review of the current results which allows

one to model in significantly more detail the flow of work or messages through a network than in

the models of Chapter 2. This area not only is interesting because of its ability to provide insight

into heavily congested systems but also because of the depth of the mathematical tools used. The

convergence theory for stochastic processes used in this area comes from some of the most

advanced work in stochastic processes. The material in this paper is of interest to even those

mathematicians who have only an academic interest in the application of stochastic processes.

So, as anyone can see from the above papers, the range of mathematical topics relevant to

computer communications is so wide that these five papers provide, at best, a tempting sample.