| Title | : | Load Balancing on Graphs with "Smart" Loads |
| Speaker | : | William Kumar Moses Jr (IITM) |
| Details | : | Wed, 30 Aug, 2017 3:00 PM @ A.M. Turing Hall |
| Abstract: | : | Load balancing is the problem of allocating n resources to n processors such that each processor is allocated one resource. It is a popular abstraction that is relevant to many problems such as scheduling processes, hashing, etc. There are many settings for this problem depending on the specific requirements of the problem, but the underlying idea remains the same. In this talk, we look at an interesting variation of load balancing on graphs. Normally, load balancing on graphs assumes that n resources are arbitrarily placed on n nodes of a graph and requires the nodes of the graph to balance resources by redistributing them to neighboring nodes. We consider an interesting variant where the loads are -smart- and can navigate the nodes themselves and perform computation in each round of a synchronous system. Such smart loads can also be considered as mobile robots and we name this problem dispersion of mobile robots on a graph.
We study this problem on both static graphs and dynamic rings. On static graphs, we analyze the time and memory trade-offs of robots achieving dispersion in trees and arbitrary graphs. We show that an increase in memory of individual robots, even by a few bits in the case of rooted trees, can dramatically reduce the time required to achieve dispersion. In the case of dynamic rings, we study rings subject to two types of dynamism: (i) vertex permutation and (ii) 1-interval connectivity. We study the ability of robots to achieve dispersion when robots are chiral/achiral and have full visibility/no visibility. |
