LFCS Seminar: Tuesday 30 September: Leslie Ann Goldberg

Title: Instability of Contention Resolution Protocols

 

 

In contention resolution, multiple processors try to coordinate sending discrete messages through a shared channel which supports limited communication. If two processors send at the same time, the messages collide and are not transmitted successfully. A contention-resolution protocol is a randomised algorithm that the processors use to decide when to send (and when to wait because the channel is too busy). The most famous example is “binary exponential backoff'' which underlies the Ethernet.  Aldous proved in 1987 that binary exponential backoff is not stable for any positive arrival rate. He conjectured the same for any contention-resolution protocol in a wide class of protocols called  “acknowledgement-based protocols''. I will give an update on the state of this conjecture. (joint work with John Lapinskas)