[talks] W Lloyd preFPO

Melissa M. Lawson mml at CS.Princeton.EDU
Tue Dec 4 11:04:41 EST 2012

Wyatt Lloyd will present his preFPO on Tuesday December 11 at 9AM 
in Room 402.  The members of his committee are;  Michael Freedman, advisor; 
Vivek Pai and David Andersen (CMU), readers; Jennifer Rexford and Margaret 
Martonosi, nonreaders.  Everyone is invited to attend his talk.  His 
abstract follows below.

Stronger Consistency and Semantics for Low-Latency Geo-Replicated Storage

Distributed data stores that support complex online applications, such
as social networks, are built with a two-level architecture. Data is
replicated across a small number of datacenters and within each
datacenter is stored in clusters of thousands or more machines. These
two levels bring different challenges for creating a scalable,
responsive, and consistent data store.

Our COPS system is the first distributed data store to guarantee the
ALPS properties—availability, low latency, partition tolerance, and
scalability—and achieve consistency stronger than eventual. Eventual
consistency specifies only that writes in one datacenter eventually
show up in the others. Causal consistency, which is what COPS
provides, maintains the partial order over operations establish by
potential causality. Under causal consistency, all of a user’s
operations appear in the order they are issued and interactions
between users, e.g., conversations in comments, appear in their
correct order as well. This improvement in consistency gives users a
better experience and makes the data store easier for programmers to
reason about. The key technical contribution of the COPS work is its
fully distributed and scalable architecture that uses explicit
metadata and off-path dependency checks to enforce ordering instead of
relying on any single point of coordination.

Our Eiger system pushes on the semantics an ALPS data store can
provide. Eiger provides high-performance, guaranteed low-latency
and write-only transactions across all the machines in a cluster.
Read-only transactions allow a client to observe a consistent snapshot
of an entire cluster. Write-only transactions allow clients to
atomically write many values spread across many servers at a single
point in time. One important use case for write-only transaction is
maintaing symmetrical relationships, e.g., Alice “isAFriendOf” Bob and
Bob “isAFriendOf” Alice should both appear or disappear at the same
time. Eiger also improves the semantics of ALPS data stores by
providing the Column-Family data model—which is used in BigTable and
Cassandra, and can be used to built real applications like
Facebook—instead of the key-value data model provided by COPS—which is
useful mainly as an opaque cache.

More information about the talks mailing list