Home
Speakers
Schedule
Location and Directions
Hotel Information
Devavrat Shah
Massachusetts Institute of Technology
Title: Aloha, that Works
Abstract: Abstact: The popularity of Aloha(-like) algorithms for resolution of contention between multiple entities accessing common resource is due to its extreme simplicity and distributed nature. For more than four decades, various researchers have established the inefficiency of the (known versions of) such algorithms to a varying degree in various setup. However, the question of designing efficient Aloha-like algorithm has remained unresolved. In this talk, we will present such an algorithm for a network of queues when contention is modeled through independent set constraint over the network graph. Key to our algorithm design is a novel ``adiabetic'' like result for queuing network and an appropriate usage of queue-sizes to make the network ``controllable''. Joint work with: S. Rajagopalan and J. Shin (both at MIT).