How self-organized criticality may lead to dynamic load-balancing
Pascal Bouvry, Frédéric Guinand, Bernabè Dorronsoro, Carlos M. C. Fernandes · 2014
This paper studies a self-organized criticality model called sandpile for dynamically load-balancing tasks arriving in the form of Bag-of-Tasks in large-scale decen- tralized system. The sandpile is designed as a decentralized agent system characterizing a cellular automaton, which works in a critical state at the edge of chaos. Depending on the state of the cellular automaton, different responses may occur when a new task is assigned to a resource: it may change nothing or generate avalanches that reconfigure the state of the system. The abundance of such avalanches is in power-law relation with their sizes, a scale-invariant be- havior that emerges without requiring tuning or control pa- rameters. That means that large—catastrophic—avalanches are very rare but small ones occur very often. Such emer- gent pattern can be efficiently adapted for non-clairvoyant scheduling, where tasks are load balanced in computing re- sources trying to maximize the performance but without as-