Theory Seminar

Abstract

A multiple-access channel is an uncontrolled communication channel such as an Ethernet. Users communicate by sending messages to the channel. If two or more users simultaneously send messages, then the messages interfere with each other (collide), and the messages are not transmitted successfully. The users use a contention-resolution protocol to resolve collisions. Thus, after a collision, each user involved in the collision waits a random amount of time (which is determined by the protocol) before resending.

Informally, a protocol is said to be ``stable'' if the messages get delivered as they arrive, without a big backlog building up. (I'll be more precise about this in the talk.)

It is still not fully understood which protocols are stable and which are not. I will survey some of the work on this question, and tell you about some recent results, which show that all ``backoff'' protocols and ``acknowledgement-based'' protocols are unstable if the arrival rate is sufficiently high.

(Joint work with Mark Jerrum, Sampath Kannan, and Mike Paterson)