Reference : The sandpile scheduler: How self-organized criticality may lead to dynamic load-balancing
Scientific journals : Article
Engineering, computing & technology : Computer science
http://hdl.handle.net/10993/16439
The sandpile scheduler: How self-organized criticality may lead to dynamic load-balancing
English
Jimenez Laredo, Juan Luis mailto [University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Computer Science and Communications Research Unit (CSC) >]
Bouvry, Pascal mailto [University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Computer Science and Communications Research Unit (CSC) >]
Guinand, Frederic mailto [Université Le Havre]
Dorronsoro, Bernabe mailto [University of Lille > Laboratoire d’Informatique Fondamentale de Lille]
Fernandes, Carlos mailto [Technical University of Lisbon > Laseeb]
2014
Cluster Computing
Springer Science & Business Media B.V.
Yes (verified by ORBilu)
International
1386-7857
[en] Optimization ; Self-organization ; Scheduling ; Distributed systems
[en] 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 decentralized 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 behavior that emerges without requiring tuning or control parameters. That means that large—catastrophic—avalanches are very rare but small ones occur very often. Such emergent pattern can be efficiently adapted for non-clairvoyant scheduling, where tasks are load balanced in computing resources trying to maximize the performance but without assuming any knowledge on the tasks features. The algorithm design is experimentally validated showing that the sandpile is able to find near-optimal schedules by reacting differently to different conditions of workloads and architectures.
FSTC-CSC/SnT
Fonds National de la Recherche - FnR
Researchers ; Professionals ; Students ; General public
http://hdl.handle.net/10993/16439
10.1007/s10586-013-0328-x
http://link.springer.com/article/10.1007%2Fs10586-013-0328-x

File(s) associated to this reference

Fulltext file(s):

FileCommentaryVersionSizeAccess
Open access
sandpileScheduler.pdfAuthor preprint863.2 kBView/Open

Bookmark and Share SFX Query

All documents in ORBilu are protected by a user license.