Article (Scientific journals)
The sandpile scheduler: How self-organized criticality may lead to dynamic load-balancing
Jimenez Laredo, Juan Luis; Bouvry, Pascal; Guinand, Frederic et al.
2014In Cluster Computing
Peer Reviewed verified by ORBi
 

Files


Full Text
sandpileScheduler.pdf
Author preprint (883.91 kB)
Download

All documents in ORBilu are protected by a user license.

Send to



Details



Keywords :
Optimization; Self-organization; Scheduling; Distributed systems
Abstract :
[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.
Research center :
FSTC-CSC/SnT
Disciplines :
Computer science
Author, co-author :
Jimenez Laredo, Juan Luis ;  University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Computer Science and Communications Research Unit (CSC)
Bouvry, Pascal ;  University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Computer Science and Communications Research Unit (CSC)
Guinand, Frederic;  Université Le Havre
Dorronsoro, Bernabe;  University of Lille > Laboratoire d’Informatique Fondamentale de Lille
Fernandes, Carlos;  Technical University of Lisbon > Laseeb
Language :
English
Title :
The sandpile scheduler: How self-organized criticality may lead to dynamic load-balancing
Publication date :
2014
Journal title :
Cluster Computing
ISSN :
1386-7857
Publisher :
Springer Science & Business Media B.V.
Peer reviewed :
Peer Reviewed verified by ORBi
Name of the research project :
Green@Cloud project (INTER/CNRS/11/03)
Funders :
FNR - Fonds National de la Recherche [LU]
Available on ORBilu :
since 27 April 2014

Statistics


Number of views
258 (6 by Unilu)
Number of downloads
421 (2 by Unilu)

Scopus citations®
 
8
Scopus citations®
without self-citations
5
OpenCitations
 
10
WoS citations
 
6

Bibliography


Similar publications



Contact ORBilu