Algorithms and Complexity Seminar

Dynamic contention resolution on a multiple access channel

Dariusz Kowalski (University of Liverpool)

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 its transmission has not overlapped with transmissions by other stations. Multiple overlapping transmissions create a conflict for access to the channel, which results in no station receiving any of the transmitted messages.

In this talk I will review approaches to resolve conflicts for access to the channel when packets are dynamically injected into the stations. The algorithms will be analyzed with respect to basic qualities of service: stability and fairness. Stability means that the number of packets waiting in queues is bounded at all times. Fairness means that each packet is eventually transmitted successfully. Dynamic packet injection is represented by adversarial models parameterized by injection rate and burstiness.