Adaptive location policies for global scheduling

Two important components of a global scheduling algorithm are its transfer policy and its location policy. While the transfer policy determines whether a task should be transferred, the location policy determines where it should be transferred. Based on their location policies, global scheduling algorithms can be broadly classified as receiver-initiated, sender-initiated, or symmetrically-initiated. The relative performance of these classes of algorithms has been shown to depend on the system workload. We present two adaptive location policies for global scheduling in distributed systems. These location policies are general, and can be used in conjunction with many existing transfer policies. By adapting to the system workload, the proposed policies capture the advantages of both sender-initiated and receiver-initiated policies. In addition, by adaptively directing their search activities toward the nodes that are most likely to be suitable counterparts in task transfers, the proposed policies provide short transfer latency and low overhead, and more important, high probability of finding a suitable counterpart if one exists. These properties allow these policies to deliver good performance over a very wide range of system operating conditions. The proposed policies are compared with nonadaptive policies, and are shown to considerably improve performance and to avoid causing system instability