Colloquium Details
Adversarial Queuing on Multiple Access Channels
| Author: | Bogdan Chlebus University of Colorado, Denver |
|---|---|
| Date: | January 29, 2009 |
| Time: | 15:30 |
| Location: | 220 Deschutes Hall, University of Oregon |
Abstract
Multiple access channels are broadcast networks with instantaneous delivery of transmitted messages to every station and a possibility of conflict for access to the transmitting medium. A message sent to a channel by a station is received successfully by all the stations when the transmission has not overlapped with transmissions by other stations. Multiple overlapping transmissions result in no station receiving any of the transmitted messages.
The traditional approach to dynamic broadcasting on multiple access channels assumes continuous packet injection subject to stochastic constraints. Inspired by recent advances in adversarial queuing theory for store-and-forward packet networks, we study stability of deterministic broadcasting on multiple access channels in adversarial settings. The framework of this work is determined by the following two methodological assumptions. First, packet injection is modeled by adversaries, which does not involve any stochastic component in the process of packet generation. Second, resolving conflict for access is performed by deterministic distributed protocols, which makes the worst-case performance of primary interest.
We consider questions regarding the achievable quality of service, in terms of protocol stability and packet latency, depending on classes of protocols and kinds of adversaries. Among positive results, we develop a protocol that achieves the maximum throughput of a packet per round for any number of stations. The protocol maintains quadratic queues, which we show to be optimal. Among impossibility results, we prove that no protocol can be both stable and guarantee that each packet is eventually successfully broadcast, for a system of at least two stations and for the maximum injection rate of a packet per round.
(This is a joint work with Dariusz Kowalski and Mariusz Rokicki, which was presented in a preliminary form at PODC'06 and SSS'07.)
Biography
Bogdan Chlebus is an associate professor with the Univeristy of Colorado Denver and the Head of the Department of Computer Science and Engineering. His research interests cover theoretical computer science, recently focusing on algorithms in distributed computing and communication networks. http://carbon.cudenver.edu/~bchlebus/