Our focus in this area is in the application of distributed search methods to resolve collisions and to identify bottlenecks in distributed systems and computer networks, and the design of efficient protocols for real-time transmissions.
We have developed an efficient collision-resolution algorithm for multiaccess networks with a geometrically distributed inter-channel access delay and an average delay that is constant, independent of the number of contending stations. In this protocol, each station chooses a random number in a common range, and stations inside a common window can contend for the channel in the next contention slot. By reducing the common window successively using dynamic programming, a single station will eventually be isolated. The speed of the protocol can be improved by storing the optimal window in each step ahead of time in lookup tables. A U.S. patent on this invention was awarded in 1986. The protocol has also been extended to use in mobile networks.
The window-based scheme for contention resolution was extended to work in multiprocessor bus networks and networks with multiple contention busses. A variation of this algorithm was implemented in the Sequent Balance 8000 multiprocessor.