Time: November 1, 2008 from 5:00 pm
Location: Hughes room
Street: 400 Cory (Hughes room), UC Berkley
Seminar Type: seminar
Organized By: U.C. Berkley
Latest Activity: November 1, 2008, 5:48 pm
he 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''.
This is based on a joint work with: S. Rajagopalan and J. Shin (both at MIT).
Add a Comment
You need to be a member to comment on this! Join Circuit Sage !