Networks of computers have become very common, so it is very important to develop methods for reliable and efficient communication between computers. One low cost scheme is to have a single shared communication medium, called a multiple access channel, such that every computer can receive all messages sent over the channel. This scheme is currently used by the Ethernet and other networks. If two or more computers send messages simultaneously, they will interfere with each other, and no useful information will be transmitted. The main goal of this research project is to develop improved probabilistic and deterministic algorithms which coordinate the computers' access to the channel so that the percentage of time in which useful information is transmitted is maximized. Also, the maximum possible percentage of useful time on multiple access channels will be determined. The algorithms for multiple access channels will be used to develop efficient algorithms for parallel computers. A second focus is to develop fast algorithms which design minimum cost network topologies that are resistant to failures.
