|Stochastic Systems Group|
Network Algorithms Made Distributed
Prof. Devavrat Shah
Resource allocation is inherent to any well engineered network. For example, resolving contention between packets accessing LAN, wireless medium or switch fabric in the router; sharing bandwidth between flows accessing the Internet; or multiplexing computational/memory resources in emerging data centers. Naturally, the algorithms allocating or scheduling resources crucially determine performance of the network. In a nutshell, to achieve efficient network utilization, such algorithms are required to solve a network-wide problem. However, in order for the network to be scalable, algorithms need to be distributed. Thus, the challenge is that of achieving a global objective through local rules under a highly dynamic environment.
In this talk, I will discuss a new method for design of distributed and dynamics aware algorithm for a generic network resource allocation problem. It builds upon insights from classical theories of reversible networks and variational principle as well as modern theory of dynamics of Markov chains. Method will be explained by means examples.
No background on the topic will be assumed and depending on the audience participation, it may be *profitable* for an attendee.
The talk is based on joint work with Jinwoo Shin, MIT.
Problems with this site should be emailed to firstname.lastname@example.org