One embodiment of the present invention provides a system that performs load balancing between task queues in a multiprocessor system. During operation, the system conditionally requests load information from a number of neighboring CPUs in a neighborhood of a requesting CPU. In response to the request, the system receives load information from one or more neighboring CPUs. Next, the system conditionally requests one or more neighboring CPUs to transfer tasks to the requesting CPU based on the received load information, thereby balancing load between the CPUs in the neighborhood.