Load Balancing in Arbitrary Network Topologies with Stochastic Adversarial Input

A simple local randomized protocol was presented and its performance on a general n-node network was analyzed. A w,λn input adversary as a process that inserts jobs in the system subject to the condition that for every sequence of w consecutive time steps, the total inserted load is at most λnw was defined. This allows the adversary to insert more jobs at some time steps, as long as the total load in windows of size w is bounded. A constrained version of the stochastic adversary by enforcing a large-deviation-type bound for the incoming load, similar to a Chernoff bound was also introduced.