-----------------------------------------------------------------------
TDS Seminar TDS Seminar TDS Seminar TDS Seminar TDS Seminar TDS Seminar
-----------------------------------------------------------------------

Title:   Work-Competitive Scheduling for Cooperative Computing with
         Dynamic Groups
Speaker: Chryssis Georgiou

Place:   NE43-308
Time:    1-2:30pm
Date:    Nov. 15, 2002

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 or even individual processors become disconnected (and,
perhaps reconnected) during the computation.
  
The efficiency of task-performing algorithms is often assessed in
terms of their work, that is the total number of tasks, counting
multiplicities, performed by 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
Omega(tg) even if each group of processors performs no more than the
optimal number of Theta(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. This paper studies algorithms for p asynchronous
processors, connected by a dynamically changing communication medium
to complete t known tasks, comparing 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.
  
This is a joint work with Alexander Russell and Alex A. Shvartsman

-----------------------------------------------------------------------