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

Title:   Rambo with Rapid Mop-Up
Speaker: Seth Gilbert

Place:   NE43-308
Time:    1-2:30pm
Date:    Oct. 25, 2002

In this talk I will present an algorithm to implement an atomic shared
memory supporting read/write operations.  Our new algorithm is based
on the Rambo algorithm of Lynch and Shvartsman, but guarantees
improved performance in badly behaved executions.  Both the original
algorithm and the new algorithm guarantee atomic consistency in all
executions, even when processes join and fail, messages are lost, and
clocks are unsynchronized.  However the Rambo algorithm takes an
unbounded amount of time to stabilize after a period of network
instability.  Our new algorithm, in contrast, will stabilize within a
constant time after the network recovers.  This rapid stabilization
allows improved performance guarantees even in less than optimal
situations.

In this talk I will first review the original Rambo algorithm.  Then I
will describe the new algorithm, and show that it still provides
atomic consistency.  Finally I will discuss the latency results in
badly behaved executions.

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