[Brown CS Talks] Brown CS Thesis Defense: Srikanta Tirthapura in Lubrano on 6/19/02 at 1 pm

[talks-admin@list.cs.brown.edu]

		  The Department of Computer Science
			   BROWN UNIVERSITY
			      
			       presents

			Srikanta Tirthapura

			    Thesis Defense
				 

		 Wednesday, June 19, 2002 at 1:00 pm

	       Lubrano Conference Room (CIT 4th floor)
		 

		    Distributed Queuing and Beyond
 

			       Abstract

Distributed queuing is a fundamental distributed coordination problem
arising in a variety of applications, such as ordered multicast and
distributed fetch-and-phi data structures.

In the distributed queuing problem, processors in a network
asynchronously and concurrently request to join a distributed queue. A
distributed queuing protocol organizes these requests into a queue,
and each request learns the identity of its successor in the queue.

In this thesis, we present the first systematic study of distributed
queuing and demonstrate its importance as a fundamental building block
in constructing distributed data structures.

We focus on the Arrow queuing protocol, a simple and popular
solution based on path reversal on a network spanning tree. The Arrow
protocol has been observed to perform well in practice, especially
under high contention to the queue. We present the first theoretical
study of this protocol's concurrent performance using competitive
analysis, showing that its performance is never far from an idealized
``optimal'' protocol. This analysis yields a surprising connection to
the nearest-neighbor Traveling Salesperson heuristic on a tree metric.

In my talk, I will first talk about the competitive analysis of the
Arrow protocol under concurrency. Next, I will discuss how to make the
protocol self-stabilizing, and hence, fault tolerant. Finally,
I will describe how to use distributed queuing in building general-
purpose parallel and distributed data structures.


		   Host: Professor Maurice Herlihy