Abstract: Contention resolution or resource allocation is a key operational (algorithmic) task that naturally arises in most of the networked scenarios. In most settings, such algorithms are required (or constrained) to be distributed and extremely simple while utilizing the resources efficiently. This tension between “implementability” and “performance” makes algorithm design (and analysis) quite challenging.
In this talk, I will discuss a novel method for designing distributed algorithms for a large class of (combinatorial) resource allocation problems that are provably efficient. As a special instance of our result, we resolve a long standing open problem about design of “Aloha-like” protocol for wireless networks. Key to our algorithm design is an “adiabetic theorem” (cf. quantum mechanics) like result for queuing networks.
Based on a joint work with J. Shin and S. Rajagopalan (both at MIT).