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

Title:   Efficient Data Replication
Speaker: Rui Fan

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

Replication is a widely used technique to improve the reliability and
performance of data services.  In most applications, replicas need to
be kept consistent with one another.  The cost of a replication
algorithm is the latency and communication costs incurred in
maintaining this consistency.  In this talk, we describe a new
fault-tolerant data replication algorithm called Layered Data
Replication (LDR), which achieves asymptotically optimal read and
write costs.  LDR separates storage of the data from storage about
where the most up-to-date data is kept.  With this technique, the data
is always in a consistent state, from the point of view of the user.
We will also discuss previous approaches at data replication, and how
LDR is a synthesis of some of those approaches.  Lastly, we discuss
two lower bounds on the cost of data replication.  One lower bound
says that users must sometimes write during a read operation.  The
other says that to make reads fast, replicas need to have unbounded
storage.

Joint work with Nancy Lynch.

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