A Gibbsian Approach to Load Balancing in Large Graphs

Vinod M. Prabhakaran
Thursday, 27 Jul 2017, 11:00 to 12:00
A-201 (STCS Seminar Room)
The talk will be on load balancing on a large graph. A unit of load on each edge of a graph is to be distributed between its nodes in a balanced way. On infinite graphs, it is known that the problem exhibits nonuniqueness. Recently, Anantharam and Salez extended the definition of balanced allocations on finite graphs to their local weak limits by exploiting the notion of unimodularity. They used this to settle a conjecture of Hajek on the Erdos-Renyi model. A more classical Gibbsian approach can also be used to arrive at the same result. This talk will highlight the key steps needed to make the classical approach work.