[Colloq] Talk **Friday, May 23, 11AM**

[Rachel Bates]

TITLE:   Distributed Queuing and Applications

SPEAKER: Srikanta Tirthapura
         Iowa State University

TIME:    Friday, May 23, 2003, 11 AM

PLACE:   CN 149

ABSTRACT:

Distributed queuing is a fundamental coordination problem, arising in a
variety of applications, such as ordered multicast and distributed
fetch-and-phi data structures. However, its significance is not well
understood, especially when compared to the closely related problem of
distributed counting.  In distributed queuing, processors in a network
asynchronously and concurrently request to join a distributed queue. A
queuing protocol queues these requests, and each request learns the
identity of its successor in the queue.

I'll first talk about a particular solution, the Arrow protocol, which is
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. The later part of the talk will
present novel applications of distributed queuing in building general
purpose distributed data structures.

(Joint work with Maurice Herlihy and Roger Wattenhofer)

Host: Rajmohan Rajaraman