Show simple item record

dc.contributor.authorGeorgiou, Chryssisen
dc.contributor.authorRussell, A.en
dc.contributor.authorShvartsman, A. A.en
dc.creatorGeorgiou, Chryssisen
dc.creatorRussell, A.en
dc.creatorShvartsman, A. A.en
dc.description.abstractThe problem of cooperatively performing a set of t tasks in a decentralized computing environment subject to failures is one of the fundamental problems in distributed computing. The setting with partitionable networks is especially challenging, as algorithmic solutions must accommodate the possibility that groups of processors become disconnected (and, perhaps, reconnected) during the computation. The efficiency of task-performing algorithms is often assessed in terms of work: the total number of tasks, counting multiplicities, performed by all of the processors during the computation. In general, the scenario where the processors are partitioned into g disconnected components causes any task-performing algorithm to have work Ω(t . g) even if each group of processors performs no more than the optimal number of Θ(t) tasks. Given that such pessimistic lower bounds apply to any scheduling algorithm, we pursue a competitive analysis. Specifically, this paper studies a simple randomized scheduling algorithm for p asynchronous processors, connected by a dynamically changing communication medium, to complete t known tasks. The performance of this algorithm is compared against that of an omniscient off-line algorithm with full knowledge of the future changes in the communication medium. The paper describes a notion of computation width, which associates a natural number with a history of changes in the communication medium, and shows both upper and lower bounds on work-competitiveness in terms of this quantity. Specifically, it is shown that the simple randomized algorithm obtains the competitive ratio (1 + cw/e), where cw is the computation width and e is the base of the natural logarithm (e = 2.7182. . . )en
dc.description.abstractthis competitive ratio is then shown to be tight. © 2005 Society for Industrial and Applied Mathematics.en
dc.sourceSIAM Journal on Computingen
dc.subjectDistributed computer systemsen
dc.subjectComputational complexityen
dc.subjectProgram processorsen
dc.subjectOn-line algorithmsen
dc.subjectCompetitive analysisen
dc.subjectIndependent tasksen
dc.subjectWork complexityen
dc.subjectDistributed computationen
dc.subjectPartitionable networksen
dc.subjectRandomized algorithmsen
dc.titleWork-competitive scheduling for cooperative computing with dynamic groupsen
dc.description.endingpage862 Σχολή Θετικών και Εφαρμοσμένων Επιστημών / Faculty of Pure and Applied SciencesΤμήμα Πληροφορικής / Department of Computer Science
dc.description.notes<p>Cited By :16</p>en
dc.source.abbreviationSIAM J Computen
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