Show simple item record

dc.contributor.authorGeorgiou, Chryssisen
dc.contributor.authorKowalski, D. R.en
dc.creatorGeorgiou, Chryssisen
dc.creatorKowalski, D. R.en
dc.description.abstractTo 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. © 2015 Elsevier Inc. All rights reserved.en
dc.sourceJournal of Parallel and Distributed Computingen
dc.subjectParallel algorithmsen
dc.subjectFault toleranceen
dc.subjectDistributed algorithmsen
dc.subjectMessage passingen
dc.subjectGrid computingen
dc.subjectTask executionen
dc.subjectTask executionsen
dc.subjectCrashes and restartsen
dc.subjectCompetitive analysisen
dc.subjectAlgorithmic solutionsen
dc.subjectCooperative computingen
dc.subjectCorrectness criterionen
dc.subjectDynamic task injectionen
dc.subjectDynamic tasksen
dc.subjectMessage passing processen
dc.subjectProcessor crashes and restartsen
dc.titleOn the competitiveness of scheduling dynamically injected tasks on processes prone to crashes and restartsen
dc.description.endingpage107 Σχολή Θετικών και Εφαρμοσμένων Επιστημών / Faculty of Pure and Applied SciencesΤμήμα Πληροφορικής / Department of Computer Science
dc.description.notes<p>Cited By :4</p>en
dc.source.abbreviationJ.Parallel Distrib.Comput.en
dc.contributor.orcidGeorgiou, Chryssis [0000-0003-4360-0260]

Files in this item


There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record