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.
Previous Page Next Page