TY - GEN
T1 - Performing dynamically injected tasks on processes prone to crashes and restarts
AU - Georgiou, Chryssis
AU - Kowalski, Dariusz R.
N1 - Funding Information:
The work of the first author is supported by research funds of the University of Cyprus. The work of the second author is supported by the Engineering and Physical Sciences Research Council [grant numbers EP/G023018/1, EP/H018816/1].
PY - 2011
Y1 - 2011
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 independent tasks that are continuously and dynamically injected to the system. The task specifications 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 be 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. 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.
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 independent tasks that are continuously and dynamically injected to the system. The task specifications 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 be 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. 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.
KW - Competitive analysis
KW - Crashes and restarts
KW - Distributed Algorithms
KW - Dynamic task injection
KW - Performing tasks
UR - http://www.scopus.com/inward/record.url?scp=80055027362&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=80055027362&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-24100-0_15
DO - 10.1007/978-3-642-24100-0_15
M3 - Conference contribution
AN - SCOPUS:80055027362
SN - 9783642240997
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 165
EP - 180
BT - Distributed Computing - 25th International Symposium, DISC 2011, Proceedings
T2 - 25th International Symposium on Distributed Computing, DISC 2011
Y2 - 20 September 2011 through 22 September 2011
ER -