Title:  Performing Work with Asynchronous Processors: 
Message-Delay-Sensitive Bounds

Speaker:  Darek Kowalski

Place:   NE43-308
Time:    1-2:30pm
Date:    Mar. 7, 2002

Abstract:

We consider the problem of performing tasks in asynchronous distributed 
settings. This problem has been substantially studied in synchronous models, 
but there is a dearth of efficient algorithms for asynchronous 
message-passing processors. The problem can be trivially solved without any 
communication by an algorithm where each processor performs all tasks.  
Assuming p processors and t tasks, this requires work \Theta(p.t). Thus it 
is important to develop subquadratic-work solutions (when p and t are 
comparable) by trading computation for communication. Following the 
observation that it is not possible to obtain subquadratic work when the 
message delay d is substantial, e.g., d = \Theta(t), this work pursues a 
message-delay-sensitive approach. We give the upper bounds on work and 
communication as functions of p, t, and d, the upper bound on message 
delays, however algorithms have no knowledge of d and they cannot rely on 
the existence of an upper bound on d.
 
We present two families of asynchronous algorithms achieving, for the first 
time, subquadratic work as long as d = o(t).  The first family uses as its 
basis a shared-memory algorithm without having to emulate atomic registers 
assumed by that algorithm. The second family uses specific permutations of 
tasks, with certain combinatorial properties, to sequence the work of the 
processors.  Finally, another important contribution in this work is the 
first delay-sensitive lower bound for this problem that helps explain the 
behavior of our algorithms.

Joint work with A. Shvartsman.