Penn Arts & Sciences Logo

Thursday, April 1, 2004 - 3:15pm

Sampath Kannan

Penn, Computer Science

Location

University of Pennsylvania

DRLB 4E9

A multiple-access channel is a broadcast channel that allows multiple users to communicate by sending messages at discrete time steps. There is no central control and if two or more users attempt to send at the same time, the messages collide and are not transmitted successfully. A contention-resolution protocol is a specification of the probability with which each message should be transmitted at each time step. The goal of such protocols is to achieve some notion of stability such as expected finite waiting time for messages. We study two popular classes of protocols -- acknowledgement-based protocols and a subclass of these called backoff protocols. We show upper bounds on message arrival rates that can be handled by these protocols in a stable manner. Our upper bounds imply that models that allow a user to observe the channels at each time step are more powerful than models that only allow a user to get acknowledgements on the success or failure of her transmissions. Joint work with Leslie Goldberg, Univ. of Warwick, Mark Jerrum, University of Edinburgh, and Mike Paterson, Univ. of Warwick.