Discrete Load Balancing in Heterogeneous Networks with a Focus on Second-Order Diffusion

摘要: In this paper we consider a wide class of discrete diffusion load balancing algorithms. The problem is defined as follows. We are given an interconnection network and number items, which arbitrarily distributed among the nodes network. goal to redistribute in iterative steps such that at end each node has (almost) same items. only allowed balance their with direct neighbors. We show three main results. Firstly, present general framework for randomly rounding flow generated by continuous schemes over edges graph order obtain corresponding schemes. Compared results Rabani, Sinclair, Wanka, FOCS'98, valid w.r.t. homogeneous first schemes, our can be used analyze larger algorithms, algorithms heterogeneous networks second Secondly, bound deviation between randomized counterparts. Finally, provide minimum initial sufficient prevent occurrence negative during execution Our theoretical complemented extensive simulations on different classes. empirically usually much faster than will not completely within reasonable time. However, maximum difference seems bounded constant value, further decreased if scheme applied once value achieved scheme.