Structure, Information and Communication Complexity

Charles R. Crawford, formerly an associate professor of computer science
at York University, is a computer-programming and mathematics
consultant.

The first Colloquium on Structural Information and Communication
Complexity was held at Carleton University in May 1994. The 10 papers
that were presented—which are published in this volume—address
problems that can arise in distributed computer systems, especially
those devoted to communication. Three of the papers deal directly with
complexity—that is, the computational power of certain network
designs— while the remaining seven deal with the routing of
information within the networks. The papers on complexity consider only
anonymous networks, in which all nodes have the same processor and the
same program. The papers on routing deal with more-general networks but
still cover only those in which all nodes have the same algorithm for
routing data packets.

These papers will be of particular interest to specialists in computer
network design. Those with some background in networks, graphs, or
topology might be interested in the concepts and strategies presented.
For example, sense of direction is a technical property, or class of
properties, of certain graphs that involves a generalization of the
ability that some people have to make the correct turn at an
intersection without referring to a map. Not surprisingly, it is
possible to find very efficient routing strategies in networks based on
graphs that have such a sense of direction.