Work-competitive scheduling for cooperative computing with dynamic groups

Abstract

The 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 width

we then show that this ratio is tight.