TY - JOUR
T1 - On the competitiveness of scheduling dynamically injected tasks on processes prone to crashes and restarts
AU - Georgiou, Chryssis
AU - Kowalski, Dariusz R.
N1 - Funding Information:
The work of first author is supported in part from research funds of the University of Cyprus (grant number UCY-ED-CG-2011 ). The work of second author is supported by the Engineering and Physical Sciences Research Council (grant numbers EP/G023018/1 , EP/H018816/1 ).
Publisher Copyright:
© 2015 Elsevier Inc. All rights reserved.
PY - 2015/8/13
Y1 - 2015/8/13
N2 - To identify the tradeoffs between efficiency and fault-tolerance in dynamic cooperative computing, we initiate the study of a task performing problem under dynamic processes' crashes/restarts and task injections. The system consists of n message-passing processes which, subject to dynamic crashes and restarts, cooperate in performing tasks that are continuously and dynamically injected to the system. Tasks are not known a priori to the processes. This problem abstracts todays Internet-based computations, such as Grid computing and cloud services, where tasks are generated dynamically and different tasks may become known to different processes. We measure performance in terms of the number of pending tasks, and as such it can be directly compared with the optimum number obtained under the same crash-restart-injection pattern by the best off-line algorithm. Hence, we view the problem as an online problem and we pursue competitive analysis. We propose several deterministic algorithmic solutions to the considered problem under different information models and correctness criteria, and we argue that their performance is close to the best possible offline solutions. We also prove negative results that open interesting research directions.
AB - To identify the tradeoffs between efficiency and fault-tolerance in dynamic cooperative computing, we initiate the study of a task performing problem under dynamic processes' crashes/restarts and task injections. The system consists of n message-passing processes which, subject to dynamic crashes and restarts, cooperate in performing tasks that are continuously and dynamically injected to the system. Tasks are not known a priori to the processes. This problem abstracts todays Internet-based computations, such as Grid computing and cloud services, where tasks are generated dynamically and different tasks may become known to different processes. We measure performance in terms of the number of pending tasks, and as such it can be directly compared with the optimum number obtained under the same crash-restart-injection pattern by the best off-line algorithm. Hence, we view the problem as an online problem and we pursue competitive analysis. We propose several deterministic algorithmic solutions to the considered problem under different information models and correctness criteria, and we argue that their performance is close to the best possible offline solutions. We also prove negative results that open interesting research directions.
KW - Competitive analysis
KW - Distributed algorithms
KW - Dynamic task injection
KW - Processor crashes and restarts
KW - Task execution
UR - http://www.scopus.com/inward/record.url?scp=84938914980&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84938914980&partnerID=8YFLogxK
U2 - 10.1016/j.jpdc.2015.07.007
DO - 10.1016/j.jpdc.2015.07.007
M3 - Article
AN - SCOPUS:84938914980
SN - 0743-7315
VL - 84
SP - 94
EP - 107
JO - Journal of Parallel and Distributed Computing
JF - Journal of Parallel and Distributed Computing
ER -