Randomized diffusion for indivisible loads

作者：

Highlights：

• Presentation of new algorithm for balancing discrete loads.

• Algorithm is very natural and avoids nodes having negative loads.

• Quality measure is the gap between maximum and minimum load, called discrepancy.

• Upper bounds on discrepancy after algorithm has run as long as its continuous counterpart.

摘要

•Presentation of new algorithm for balancing discrete loads.•Algorithm is very natural and avoids nodes having negative loads.•Quality measure is the gap between maximum and minimum load, called discrepancy.•Upper bounds on discrepancy after algorithm has run as long as its continuous counterpart.

论文关键词：Distributed computing,Load balancing,Diffusion,Randomized algorithms,Random walk

论文评审过程：Received 3 December 2010, Revised 31 March 2014, Accepted 17 April 2014, Available online 5 June 2014.

论文官网地址：https://doi.org/10.1016/j.jcss.2014.04.027