Fast algorithms for distributed resource allocation
I. P. Page, Tom Jacob, E. Chern · IEEE Transactions on Parallel and Distributed Systems · 1993
Two new algorithms for the distributed static resource allocation problem are presented. The first algorithm, which shows excellent average case behavior in simulation requires the maintenance of a global queue. The second, which needs only local communication, has polynomial waiting time and exhibits better average case behavior than the only other known polynomial time algorithm. Both algorithms have polynomial message complexity.>