University of Michigan

Purdue Research Foundation

Harsha Honnappa

Vijay Subramanian

A load balancing method is disclosed, the method includes establishing a processing network including a plurality of task-processing processors interconnected therewith, each processor of the plurality having a queue of tasks to be processed, establishing a k-regular graph including nodes and branches connecting the nodes, where k is the degree of the graph, assigning d walkers to the k-regular graph, where each walker is randomly assigned to a node, receiving a new task to be processed, walking from the assigned nodes to new nodes by randomly choosing a new node from one or more available nodes, without backtracking from each of the assigned nodes to a node from which each of the d walkers immediately walked, comparing the queues of the new nodes, determining which queue of the new nodes has the least number of tasks; and assigning the new task to the node with the least number of tasks.

Growing community of inventors

West Lafayette, IN, United States of America

Harsha Honnappa