Convergence to Equilibria in Distributed, Selfish Reallocation Processes with Weighted Tasks

摘要

We consider the problem of dynamically reallocating (or rerouting) m weighted tasks among a set of n uniform resources (one may think of the tasks as selfish agents). We assume an arbitrary initial placement of tasks, and we study the performance of distributed, natural re-allocation algorithms. We are interested in the time it takes the system to converge to an equilibrium (or get close to an equilibrium). Our main contributions are (ⅰ) a modification of the protocol in [2] that yields faster convergence to equilibrium, together with a matching lower bound, and (ⅱ) a non-trivial extension to weighted tasks.