Computer networks have become very common. It is very important to develop methods which allow computers to efficiently communicate with each other. One low cast 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 Ethernet and other networks. If two or more messages are sent simultaneously, they will interfere with each other, and no useful information will be transmitted. Efficient use of the communication channel requires a coordination scheme which allows one computer at a time to transmit. The main goal of our research project is to develop improved probabilisitic 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. In addition, we plan to show that the algorithms employed are nearly optimal, which will demonstrate the maximum possible effectiveness of multiple access channels. We will also develop algorithms for multiple access channels which give computers on the network more information. Our results on the performance of this more powerful channel will indicate the effectiveness of improved channel technology.
