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 setting where the computing medium is 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 their work: the total number of tasks, counting multiplicities, performed by all of the processors during the computation. In general, an adversary that is able to partition the network into g components can cause 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 such pessimistic lower bounds, and in order to understand better the practical implications of performing work in partitionable settings, we study distributed work-scheduling and pursue a competitive analysis. Specifically, we study a simple randomized scheduling algorithm for p asynchronous processors, connected by a dynamically changing communication medium, to complete t known tasks. We compare the performance of the algorithm against that of an "off-line" algorithm with full knowledge of the future changes in the communication medium. We describe a notion of computation width, which associates a natural number with a history of changes in the communication medium, and show both upper and lower bounds on competitiveness in terms of this quantity. Specifically, we show that a simple randomized algorithm obtains the competitive ratio (1 + cw/e), where cw is computation widthen
dc.description.abstractwe then show that this ratio is tight.en
dc.sourceConference Proceedings of the Annual ACM Symposium on Theory of Computingen
dc.source35th Annual ACM Symposium on Theory of Computingen
dc.subjectDistributed computer systemsen
dc.subjectComputer supported cooperative worken
dc.subjectOn-line algorithmsen
dc.subjectCompetitive analysisen
dc.subjectIndependent tasksen
dc.subjectWork complexityen
dc.subjectDistributed computationen
dc.subjectPartitionable networksen
dc.subjectRandomized algorithmsen
dc.subjectWork-competitive schedulingen
dc.titleWork-competitive scheduling for cooperative computing with dynamic groupsen
dc.description.endingpage258 Σχολή Θετικών και Εφαρμοσμένων Επιστημών / Faculty of Pure and Applied SciencesΤμήμα Πληροφορικής / Department of Computer Science
dc.type.uhtypeConference Objecten
dc.description.notes<p>Sponsors: SIGACT, ACMen
dc.description.notesConference code: 61250en
dc.description.notesCited By :6</p>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