►
From YouTube: CRDTs in Practice - Marc Shapiro & Nuno Preguiça
Description
Slides and more info: http://www.codemesh.io/codemesh2015/marc-shapiro
The CRDT abstraction (Conflct-free Replicated Data Type) is a useful tool for building highly scalable and available applications. CRDTs combine three key intuitions: (i) Encapsulate distribution inside the boundaries of a data type, so that ordinary programmers can build applications by combining CRDTs from a library; (ii) support "write now, propagate later" concurrent updates to ensure scalability, availability and performance; (iii) some simple of mathematical properties that ensure that data replicas converge safely. This talk presents the principles and design of some useful CRDTs. We discuss the CRDT approach in the context of some real applications of our industrial partners. We present some of the difficulties and limitations of CRDTs, in the more general perspective of consistency and scalability. We present recent extensions that address some of these limitations, in particular formaintaining application invariants.
Marc Shapiro does his research on distributed computer systems, data replication and consistency algorithms, and distributed garbage collection. He invented the proxy concept, which is now universal on the Internet. He published at SOSP and OSDI, the two most prestigious venues of the area (one of the only two French papers at both venues). He was instrumental in the creation of EuroSys, the main European venue in the area. He authored 64 international publications, 17 recognised software systems, and four patents. Dr Shapiro's research started with a PhD from Université Paul Sabatier for research performed at atLAAS in Toulouse, France (1980), followed by a post-doc at MIT, and a researcher position at CMIRH. He is a researcher at INRIA since 1984. He spent a one-year sabbatical at Cornell (1993—1994), and he led the Cambridge Distributed Systems group at Microsoft Research Cambridge (UK) from 1999 to 2005. He is currently a Senior Researcher for INRIA Paris-Rocquencourt, in the Regal group, located at LIP6.
Nuno Preguiça is curently Associate Professor at FCT - Univ. NOVA de Lisboa and leads the Computer Systems group at NOVA LINCS. He does research in the area of distributed systems, mobile computing and data management. He co-proposed the concept of CRDTs and a number of extensions to CRDTs, including variants for enforcing global invariants and for efficient execution of distributed computations.
A
So,
as
he
said,
I'm
Mark,
Shapiro
I'm
work
in
Paris
at
in
real
and
at
the
University,
the
Science
University
I'm
Ali
Cooley
over
there.
So
today
we
will,
with
nuno,
will
tell
you
a
little
bit
more
about
your
duties.
I
assume
that
most
of
you
have
read
the
papers,
so
we
would
not
go
too
much
into
the
detail
of
what
a
co
DG
is,
but
more
about
the
design
philosophy
and
what
we've
learned
in
the
past
few
years.
A
A
So
for
all
these
reasons,
you're
going
to
replicate
the
data
in
different
places,
move
the
data
as
close
as
possible
to
the
users,
have
your
application
logic
running
next
to
the
data
next
to
the
database
and
in
order
to
have
availability,
you
want
to
be
able
to
accept,
reads
and
updates
at
all
the
different
replicas
without
synchronizing,
because
synchronizing
is
costly
and
is
not
available
if
there's
a
problem.
So
this
is
where
our
starting
point
and
the
what
we've
been
trying
to
do
is
you
know,
make
this
a
lot
easier
for
for
programmers
move
to.
A
So
you,
of
course,
you
we
all
know
about
key
value
stores
and
and
no
sequel,
databases
where
we're
trying
to
move
one
level
up
to
higher
level
abstractions
that
are
more
useful
to
the
user
to
the
developer,
and
another
thing
we
want
to
do
is
look
to
the
future.
So
today
there
might
be.
You
know
a
few
tens
of
data
centers
around
in
the
world,
but
this
is
changing
very
quickly
and
there's
more
and
more
and
more,
you
know
locations
for
your
data
that
are
possible.
A
You
know
from
keystroke
to
or
mouse
movement
to
to
to
to
response
and
what
we
want
to
do
is
we
want
to
move
the
guarantees
that
we
might
give
today
in
in
the
data
centers
to
those
replicas
very
close,
so
you
know
we're
not
there
yet,
obviously,
but
sometime
in
the
future,
we'll
have
to
be
able
to
manage.
You
know
tens
of
thousands
of
replicas
and
and
of
course,
do
that
in
a
fault-tolerant
way.
A
A
A
Of
course
it's
replicated
at
multiple
nodes,
but
the
way
it's
replicated
is
that,
in
order
to
ensure
availability,
first
of
all,
we
were
always
ready
to
accept
updates.
So,
therefore,
updates
can
be
concurrent
and
non
synchronized,
but
we
still
guarantee
that
your
data
will
eventually
converge
and
it's
not
just
registers
that
do
reads
and
writes
it's
higher-level
data
types
such
as
sets
or
graphs
or
sequences,
or
you
know,
complex
things
that
are
much
more
useful
for
application.
Programmers
and
I
will
not
go
into
the
details
of
how
we
prove
this,
but
it's
in
the
papers.
A
A
So
why
would
anybody
use
these
data
types
well,
first
of
all,
because
if
they
ensure
availability,
if
you,
if
it
availability,
is
not
your
prime
motive
in
life,
I
mean
forget,
sorry,
T's
and
forget,
parallelism,
you
know,
might
as
well
do
things
sequentially,
it's
a
lot
easier,
a
lot
simpler
and
much
more
familiar.
So
if
you
know
availability
is
your
thing,
then
maybe
surgery,
T's,
is
something
you
want
to
look
at.
A
Surgery,
T's
are,
as
I
said,
higher
level
data
types.
So
if,
if
you
don't
need
higher
level
data
types
right,
if
ret
just
you
know,
readwrite
registers,
key
value
stores
are
okay
for
your
application
by
all
means.
Stick
with
that,
but
you
know,
if
you
have,
if
you,
if
you
have
like
I,
don't
know
some
distributed
game
with
game
state
that
is
highly
mutable
and
highly
distributed
over
these
ten
thousand
replicas
again.
Maybe
this
is
the
way
something
you
meet.
You
should
be
looking
at
mobile
computing.
A
There's
another
example,
because
you
know
your
mobile
computers
might
be
completely
disconnected
from
the
network
and
you
want
to
be
able
to
do
your
region
and
updates,
even
though
you're
disconnected
and
be
sure
that
you're
going
to
reconverge.
When
you
reconnect,
it's
also
useful
in
listen
within
the
data
center
to
have
more
parallelism
inside
the
data
center,
avoid
avoid
synchronization.
A
So
some
of
the
concepts
some
of
the
design
ideas
so
first
of
all,
these
are
data.
Types
that
are
supposed
to
be
familiar
so
acidity
set
should
look
as
closely
as
possible
to
your
sequential
set
right
and
has
the
same
operations
to
add
and
remove
elements
in
the
set
and
a
graph
should
look
like
the
graphic
cetera.
But
of
course
you
know,
if
you
want
concurrency,
then
you
have
to
do
some.
You
have
to
accept
some.
A
You
need
to
lower
your
expectations.
Some
odd
okay,
but
anyway,
you
need
to
be
the
sort
of
top
level
bit.
Is
you
need
to
be
backward
compatible
with
sequential
data
types?
This
is
not
written
into
the
papers.
It's
so
obvious
that
we
never
stated,
but
it's
actually
a
very
important
property
and
the
second
principle
is
you
want
your
operation
to
commute
okay,
because
if
you
have
operations
that
updates
the
commute
right,
then
it
doesn't
matter
which
order
they're
received.
A
So
if
I
do
you
know
some
operation
up
here
you
and
that's
other
operation
down
here
V
somebody
might
receive
you
followed
by
V.
Somebody
else
might
be
receive
V,
followed
by
you,
but
it
shouldn't
matter
right.
So
if
your
operations
already
commute
in
the
sequential
data
type
you're
home
free
right,
so
you
have
things
like
you
know.
A
If
I'm
talking
about
a
set,
I
have
operations
like
adding
an
element
II
and
removing
a
set,
a
different
element:
F,
okay,
that
commutes,
because
a
D
followed
by
remove
F,
you
know,
ease
in
the
set
F
is
not
in
the
set,
and
that's
true,
even
if
you
swap
the
two
so
naturally
concurrent
a
D
and
remove
F
should
have
exactly
the
same
semantics.
Okay.
A
That's
really
the
destroy
the
assent
essence
of
sorority's,
but
it
also
should
be
explainable
to
users
and
developers.
So
you
want
it
to
be
as
close
as
possible
to
one
of
the
sequential
executes.
It
cannot
be
exactly
the
same.
Okay
and
sometimes
the
anomalies
will
show
through.
But
you
know
it
should
be
close
enough.
Let's
say:
there's
no,
there's
no
good
measure,
but
close
enough.
A
A
A
So
sororities
are
a
an
academic
concept
that
were
published
in
2009
and
the
main
paper
is
2011,
but
they've
been
picked
up
by
by
industry,
and
these
are
some
of
the
companies.
Well,
these
are
the
companies
that
we
know
about
that
have
announced
in
some
way
or
another
that
are
actually
using
CRT
T's
internally.
So
we
must
be
doing
something
right
here
and
I
will
talk
about
one
of
these
guys
and
I.
There's,
probably
some
people
from
bet365
in
the
room,
so
they
they
will
correct
me
if
I
say
anything
stupid
this.
A
This
is
knowledge,
I
know
from
their
website,
and
you
know,
videos
that
they
posted
I
don't
have
any
particular
insight,
knowledge,
okay,
but
okay.
So
these
these
are
apparently
they
say,
the
largest
European
online
betting
operator,
and
they
have
a
very
bursty
low.
They
have
up
to
two
and
a
half
million
users
at
any
point
in
time.
Simultaneous
users
banging
on
their
data,
one
terabyte
working
set
I'm,
not
sure.
A
What's
in
that
working
set,
but
I
I
know
that
a
substantial
fraction
of
that
working
set
is
actually
stored
in
C
our
duties
and
sort
of
the
the
top
level
requirements
is
for
them
is
that
has
to
be
available,
so
users
have
to
be
able
to
place
their
bets
at
any
point
in
time
in
whatever
their
soccer
game,
and
you
know,
even
if
they,
even
if
one
of
their
server
fails,
and
they
also
want
some
the
results
to
be
understandable.
So
just
eventual
consistency
is
not
good
enough.
You
have
to
have
some
kind
of
monotonicity.
A
That
is,
if
I
made
a
bet
and
I
look
at
the
database.
I
should
be
able
to
see
my
bed
right
or,
if
I
read
somebody's,
you
know
some
results.
Somebody
made
the
bet
a
minute
later.
I
should
look
at
the
database
and
still
find
it
there
right
there.
You
don't
get
those
guarantees,
if
you
just
ask
for
eventual
consistency,
and
they
want
transparency,
that
is,
they
want
the
results
to
be
explainable
to
users.
So
again.
A
This
is
why
I
think
probably
the
reasons
why
they
they
chose
to
look
at
CEO
duties
and
in
the
old
days,
a
few
years
ago,
they
used
sequel,
server
and
found
that
that
didn't
that
didn't
scale
at
all
and
that
when
they
had
a
failure,
it
took
hours
for
the
sister
to
reconvert
and
mid-2013.
They
decided
to
look
at
react,
which
is
no
sequel
database,
which
was
fine
in
terms
of
availability,
but
when
a
failure
would
occur,
there
was
come
up
with,
they
would
have
siblings,
and
this
was
really
so
so.
A
Multiple
values
to
the
same
data
item,
which
was
very
hard
for
them
to
to
deal
with
manually.
So
at
some
point
they
decided
to
look
at
CEO
duties
and
they're
actually
using
strategies
in
production
since
almost
a
year
now,
and
what
they're
using
is
the
observe,
remove,
set
that
it
has
been
implemented
by
by
Russell
in
in
react
and
again
I.
A
You
know
anomalies
in
distributed
systems,
and
whenever
there
was
a
failure,
it
would
reconverge
very
quickly
incorrectly
and
I
asked
them.
You
know
what
what
would
they
like
for
the
future
what's
their
wish
list
and
so
that
the
wish
list
is
more
of
the
same
right.
So
they
would
like.
You
know
the
same.
You
know
availability
and
all,
but
you
know
a
little
bit
more
guarantees
about
you
know.
Maybe
I
want
to
update
two
things
at
once
and
not
just
a
single
set.
A
So
I
already
talked
a
little
bit
about
this.
I
can
skip
this
slide,
so
sets
is
sort
of
the
you
know
poster
child
of
absurdities,
and
this
is
the
thing
that
everybody's
been
looking
at,
but
I
didn't
want
to
make.
It
is
too
boring.
So,
let's
invent
a
new
data
type:
okay,
a
new
serie
DT
right,
so
you're
starting
a
you.
Have
this
idea
for
a
new
startup
you're
going
to
manage
wedding
lists
for,
for
you
know,
people
who
get
married
and
everybody
will
have
a
copy
of
their
wedding
list
on
their
iPhone
and
okay.
A
So
here's
my
wedding
list.
It
has
you
know,
I
want
a
TV
and
I
want
and
I
want
to.
You
know
my
honeymoon
in
Venice
and
it's
an
ordered
list
as
TV
and
you
know,
buying
the
TV
is
more
important
to
me
than
than
going
to
Venice
and
then
of
course
I
might
do
you
know
add
things
so
I
will
point
at
one
of
the
items
in
my
list
and
I
will
say
well
I'm,
going
to
add
something
right
after
this
one.
Okay.
So
what
looks
less
important
going
to
do?
A
Venice
and
after
all
know,
maybe
I
don't
want
to
go
to
Venice,
so
I
will
delete,
pointed
Venice
and
say
delete
right,
and
then
you
know
my
spouse
to
be
on
her
replica
will
also
pointed
Venice.
She
doesn't
know
that
I
deleted
Venice
because
we're
working
independently
and
on
different
replicas.
So
she
points
at
Venice
and
says.
A
Well,
you
know
I
would
also
like
to
go
on
a
ski
trip,
but
you
know
then
it's
still
more
important
to
me
and
then
at
some
point
you
know
the
data
will
be
exchanged
and
will
we
converge,
and
now
you
see
that
Venice
is
gone
right
and
that
all
the
things
that
I
have
added
are
in
there
and
they're
in
the
right
order?
Okay,
so
yeah,
so
you
know
here's
the
here's.
The
specification
I
want
to
be
able
to
look
up
the
contents
of
my
wish
list.
A
I
want
to
be
able
to
add
a
wish
to
my
list
and
I
want
to
remove.
You
know
something
from
my
list
easy
enough.
So
how
can
I
implement
that?
Well,
basically,
you
know
it's
a
linked
list
right,
I'm,
adding
and
removing
elements
to
a
sequential
linked
list
has
a
beginning
marker
and
an
end
marker
and
every
time
I
want
to
add
something.
It
will
just
say
add
after
this
position
right.
A
You
know
you,
you
all
know
how
to
do
linked
lists
and
then
I
can
do
the
same
thing:
I'll
insert
books
and
then
maybe
concurrently,
you
know,
oh
no
and
then
I'm
deleting
Venice,
okay,
so
deleting
I
I'm
not
allowed
to
remove
Venice
from
the
list
immediately,
because
my
spouse
by
me
it
might
be
adding
things
after
Venice
right,
which
is
exactly
what
happened
in
that.
In
the
example,
I
showed
you
so
I
can
still
insert
the
ski
trip
that
there
at
the
right
position.
Okay,
so
what
happens?
A
So
we
have
to
resolve
this
just
any
any
any
way
of
resolving.
It
is
okay
as
long
as
it's
deterministic
right,
so
let's
just
resolve
it
by
by
alphabetical
order
and
we're
done.
Okay
and
there
you
have
their
data
types
that
you
need
it
for
for
linked
lists,
so
I
cheated
I
didn't
really
invent
this.
This
is
called
RGA
and
it's
been
in.
It
is
in
one
of
the
co
DT
publications,
but
it's
a
little
bit
of
secure
okay.
So
maybe
we
can
improve
this
right.
A
So
no,
this
looks
wrong.
Right,
I
mean
world
peace
definitely
cannot
be
important
than
than
buying
a
drone
right.
I
want
to
move
world
peace
up
to
the
top
right,
but
simultaneously
my
spouse
says
Oh
world
peace.
This
is
doesn't
make
any
sense.
You
know
world
peace
is
not
achievable,
so
it
doesn't
belong
at
the
top
of
the
list.
I'll
move
it
to
the
bottom
right
and
well.
We
end
up
now
with
world
peace
in
duplicate
of
course,
okay,
so
something
went
wrong
here
all
right.
This
is
something
that
you
know.
A
I
asked
for
move
right,
I
asked,
which
implicitly
means
this
thing
cannot
be
in
two
places
at
the
same
time,
if
it
is
in
two
places
at
the
same
time,
by
the
way
I've
messed
up
my
linked
list,
but
you
know
that's
just
a
technical
question,
so
in
effect
I've
just
added
you
know
two
copies
of
world
peace
and
and
removed
the
the
single
ones,
so
I
didn't
get
what
I
wanted
and
the
other
thing
of
course
I
would
like
to
do.
Is
you
know
now
that
I
have
my
wedding
lists?
People
are
gonna.
A
A
Russell
who
really
likes
likes
my
spouse
also
says
oh
I'm
going
to
buy
you
the
Hydra,
and
we
end
up
with
two
copies
of
the
I
drone
right,
which
again
is
not
what
we
wanted.
So
what
happened
here?
So,
what's
the
difference
between
remove
which
just
marked
something
is
being
removed
and
offer
which
also
this
mark
something
is
being
offered?
Okay?
Well,
there's
a
big
difference.
The
so
here.
I'm
writing
a
specification
sort
of
the
triple
style
so
here,
I,
have
an
operation
removed
and
then
to
the
left
is
the
precondition.
A
The
things
that
have
to
be
true
before
I
apply
this
operation
and
so
the
right
to
post
condition
the
things
that
should
be
true
afterwards
right.
So
when
I
remove
I
expect
the
thing
that
I've
removing
to
be
marked
as
a
tombs
okay,
but
it
doesn't
really
matter
what
the
state
is
before,
even
if
it
was
a
tombstone
before
it's
okay
right.
So
there
is
no
no
real
precondition,
but
its
bark
is
true
here,
whereas
in
the
move
case
or
in
the
offer
case,
I
want
to
make
sure
that
the
item
is
unique
right.
A
So
this
invariant
that
this
this
item
appears
only
once
right
comes
out
in
this
precondition
right,
so
in
a
sequential
execution,
if
I
want
to
offer
something,
I
make
sure
that
it
hasn't
been
offered
before
right.
So
I
have
this
precondition.
It's
not
offered
yet
and
I
offer
it,
and
therefore
afterwards
it
will
be
in
the
offered
State.
But
now
you
see
just
looking
at
this,
you
see
that
if
I
have
two
concurrent
offers
executing
one
of
these
offers
is
going
to
violate
the
precondition
that
the
other
one
okay.
B
A
This
is
really
the
reason
why
move
or
offer
didn't
work.
Okay,
I'm
trying
to
maintain
an
invariant
and
in
order
to
maintain
that
is
invariant
I
need
a
I
need
a
precondition,
but
the
concurrent
operation
is
violating
that
precondition.
So
I'll
say
that
the
precondition
is
not
stable,
so
and
people
who
who
came
to
our
tutorial
yesterday.
We
explained
this
in
a
little
bit
more
detail,
but
basically
there's
a
proof
that
says
that
if
all
the
invariants
are
sorry,
if
all
the
preconditions
are
stable
under
all
concurrent
updates,
then
the
invert
is
guaranteed.
A
But
if
not
all
bets
are
off
so
see
lessons
learned
before
I
pass
the
mic
to
you
know.
So,
if
you
want
availability,
you
have
to
accept
concurrent
updates
and
you
know,
there's
undesirable
effects,
but
you
can
often
mask
those
invariable
undesirable
effects.
So,
for
instance,
if
I,
if
I
add
the
same
thing
twice:
okay,
it's
okay
right,
I
can
accept
them
both
and
just
sort
of
hide.
The
second
item
I
want
to
be
backwards
compatible.
So
this,
if
any
any
secret.
A
If
two
operations
commute,
then
I
want
the
concurrent
semantics
to
be
the
same,
but
otherwise
I
have
to
choose
something
that
is
deterministic
again
and
close
enough
and
I'm
maintaining
that
if
I
want
to
maintain
invariance,
this
is
something
really
new
that
is
not
in
the
papers.
If
you
want
to
maintain
some
invariance,
then
the
the
thing
you
need
to
mean
sure
is
that
your
preconditions
are
stable.
C
Okay,
so
now
I
will
try
to
explain
you
how
we
can
maintain
some
of
the
invariants.
So
if
you
look
at
the
manipulations,
so
many
applications
need
to
24
invariants
of
the
form.
Kind
of
some
counter
must
be
greater
or
equal
to
K,
for
example,
if
we
are
counting
the
number
of
ad
impressions
in
a
in
an
application
that
has
some
amount
of
ads
to
print,
so
the
number
of
impressions
left
must
be
greater
or
equal
to
zero.
C
If
we
keep
put
many
afikoman
in
again,
okay,
we
want
too
many
to
be
greater
or
equal
to
zero.
Of
course,
if
it's
real
many,
we
also
wanted
to
the
bank
also
wants
the
money
that
you
have
in
the
bank
account
to
be
greater
or
equal
to
zero.
So
it's
exactly
the
same
problem.
So
how
can
we
try
to
to
address
this
problem?
C
One
thing
that
it
is
important
to
understand
is
that
if
you
are
trying
to
do,
for
example,
to
keep
the
number
of
impressions
left
greater
or
equal
to
zero
most
of
the
times,
we
don't
have
problems.
If
the
number
of
impressions
left
are
one
thousand
or
twenty
thousand
or
something
like
that,
so
the
cremating
by
one
well,
it
will
not
make
it
under
zero.
Okay,
so
only
when
we
are
closing
to
zero
to
zero.
We
we
get
into
into
problems,
okay,
so
to
try
to
address
these
these
numeric
invariants.
C
What
we
do
is
we
try
to
see
the
current
value
of
the
counter.
Okay,
as
the
number
of
Rights
twins
acute,
a
decrement,
for
example,
if
X,
if
I,
have
a
counter
X
and
then
fell
off
the
counter,
for
example,
is
1000.
That
means
that
I
have
1000
rights
to
twins
acute
decrement,
okay
and
these
1000
rights
to
execute
decrement
and
HIDA
Street
these
rights
by
multiple
replicas,
okay.
So
every
time
I
is
equal
to
decrement,
I
will
consume
when
right.
Every
time
is
acute.
An
increment
I
create
a
new
right.
C
Okay,
so-
and
this
is
the
the
key
IDF
to
to
to
enforce
these
numeric
invariants
okay-
we
will
have
this
right.
We
will
distribute
these
rights
among
replicas
and
we
want
to
not
consume
more
rights
than
then.
Then
it
exists,
okay,
so
the
problem
now
is.
We
could
do
that
using
a
central
server.
You
would
go
to
the
central
server
see
if
there
is
any
right
over
wall-
okay,
but
we
don't
want
to
do
this.
Okay.
C
What
we
would
like
to
do
is
to
distributed
these
among
multiple
replicas
so
that
each
replica
can
can
access
the
counter
independently.
Just
like
it
is
a
CR
DT.
Okay,
so
it's
replica
is
it's
it's
copy!
F
of
this
object.
It's
replicas
execute
operations.
Locally
replicas
will
synchronize
peer-to-peer
as
any
other
Theory
T,
okay,
so
using
the
normal
rules.
If
we
have
stuck
biased,
ER
duties
will
send
this
light.
We
will
do
the
merge,
as
in
any
other
CR
DT.
Okay.
There
is
a
slight
difference.
C
Okay,
so
if
we
don't
want
the
counter
to
be
negative,
sometimes
when
we
use
acute
an
operation
locally,
the
operation
will
will
have
to
file.
So
I
will
try
to
decrement,
and
my
replica
will
tell
me:
okay,
you
cannot
decrement,
because
if
you
decrement,
we
might
break
the
invariant
okay,
the
only
difference
when
compare
it
with
a
normal
city
in
which
you'll
be
allow
it
to
decrement,
but
you
could
go
negative
okay,
so
we've
built
a
reality
that
is
call
it
the
bounded
counter
DePandi's
counter.
Basically,
you
can
create
about
it
counter.
C
You
have
one
operation
to
increment
a
value
even
operation
to
decrement
a
given
value.
You
can
see
the
current
value
in
your
bonded
counter
and
you
can
transfer
rights
from
one
replica
to
another
replica.
Okay,
so
I
can
give
rights
to
another
replica.
I
will
I
will
now
show
how
this
works
so
so
this
is
a
bit
scary.
Okay,
so
basically
we
have
our
our
CR
dt.
Supposing
that
we
have
three
replicas:
okay
as
a
matrix,
each
line,
its
corresponds
to
an
replicas.
C
Each
column
corresponds
to
an
replicas,
okay
and
now
I
will
show
how
we
updated
this
matrix.
So
we
start
with
all
zeros,
meaning
that
Kira
was
the
counter,
is
zero.
Okay
and
now
I
can
increment
in
in
the
first
replica
when
I
increment
in
the
first
replica,
okay
I
will
write
the
the
matrix
in
the
position:
1
1,
okay,
if
I
increment
in
the
second
replica
I,
will
use
the
second
line.
C
C
So
now
we
want
to
do
the
comments.
Ok,
we
have
done
increments.
We
can
always
do
increments.
No
problem.
Ok,
now
I
want
to
do
a
decrement,
so
in
first
replica
I
want
to
decrement
by
15.
I
will
not
explain
at
this
moment.
I
will
check
if
we
can
decrement
by
15
or
not,
but
we
know
that
we
cannot
because
in
that
replica
of
only
incremented
by
10
I
have
not
synchronized
with
replicas.
So
this
will
have
to
fail.
Okay
later
on,
I
will
explain.
I
really
understand
that
it
needs
to
fail.
C
C
So
I'll
do
idea
to
a
transfer
so
in
the
sort
of
replica
I
have
incremented
by
eight.
So
that
means
that
I
have
eight
rights
to
do
decrement.
Okay,
so
suppose
now
I
want
to
transfer
some
of
these
rights
to
replica
one
okay
that
wanted
to
decrement
more
than
ten,
so
I
want
to
transfer
for
rights
to
replica
one.
So
what
do
I
do
is
I
will
update
that
information
in
my
in
my
matrix.
Okay,
basically,
I
use
the
last
line,
so
replicas
free
will
always
uses
this
line.
C
So
this
is
how
I
update
the
the
matrix
when
I
do
increments
or
transfers
or
decrements.
Okay,
so
all
the
way
merge.
So
in
CID
T's,
when
we
do
a
merge,
we
seen
the
state
of
one
replicate
within
the
replica.
Okay
and
in
these
guys
merging,
is
pretty
simple.
It's
pretty
simple,
because
each
replica
only
modifies
its
its
line;
okay,
no
other!
So
in
the
first
line,
only
replica
one
touch
on
the
second
line
only
replicate
two
touches
on
third
line.
C
C
So
now,
let's
look
again
how
we
really
handled
the
comments.
So
so
now
we
have
the
this
value.
Okay,
the
this
value
of
the
depended
counter
and
I
want
to
do
a
decrement
by
f12,
okay,
how
do
I
know
that
whether
I
can
do
with
the
comment
of
12
or
not
so
I
need
to
check
if
I
have
12
or
more
rights
to
do
the
comments?
C
Okay,
and
to
do
this
basically,
what
I
do
is
I
will
add
the
Iowa
at
the
the
position
when,
when
in
the
matrix
that
those
are
the
values
that
I've
incremented
okay,
so
those
are
the
the
rights
that
I've
created.
Okay
I,
add
the
values
in
the
in
the
in
the
column,
the
other
values
in
the
column.
Those
are
the
rights
that
some
replicas
transfer
to
me,
so
that
for
means
that
replica
three
transferred
for
rights
to
me
so
I
have
fourteen
rights.
C
Okay
and
I
have
to
decrement
the
values
that
I've
transferred
to
other
replicas
and
that
I've
consumed
in
this
guy's
I
have
not
consumed
any
other
any
value.
So
far,
so
in
fact,
I
have
fourteen
rights
available.
So
I
can
is
acute
depression
locally
and
guarantee
that
I
I
can
decrement
and
by
the
commenting
that
the
the
value
of
the
country
will
not
go
negative,
okay,
so
Oh.
C
What
can
we
do
when
you
use
bonded
cutters?
Basically
in?
In
summary,
we
execute
operations
locally.
So
if
there
is
no
enough
rights,
we
file
locally.
Of
course
we
can
try
to
transfer
rights
from
other
replicas
at
that
moment.
Okay,
so
we
can
redistribute
it
right
proactively.
Okay,
replicas
can
be
transferring
rights
among
them
or
they
can
transfer.
When
I
do
a
decrement
and
I
don't
have
enough
rights.
C
Bicyclist
inconsistency
in
with
this
approach
is
having
a
single
single
data
center
and
all
updates
will
go
to
that
data
center.
Okay,
so
latency
is
the
very
slightest
is
pretty
high,
because
some
of
the
updates
have
to
the
cross
to
some
other
data
center,
and
we
are
using
this
case.
We
are
using
the
stone
consistency,
approach
of
react
so
performance.
C
It
doesn't
scales
to
very
large
numbers.
Well,
we
have
not
so
many
keys.
If
we
had
more
keys,
probably
it
will
scale
more,
but
this
is
so
for
anything
apples
to
apples
comparison.
This
is
what
we
have
so
if
we
have,
if
we
have
we
consistency-
and
this
is
react
with
react-
counters
okay,
basically,
we
have
much
higher
throughput
and
much
lower
latency.
Basically,
each
point
of
this
was
is
taken
by
incrementing
number
of
clients,
so
for
some
given
number
of
clients,
I
can
achieve
some
throughput
with
a
given
average
latency.
C
C
C
Okay
and
what
of
what
we
also
have
when
compared
with
we
consistency
is
that
we
guarantee
that
that
evidence
will
not
be
broken
while
when
you
use
only
weak
consistency
when
you
are
closing
to
the
limits,
the
even
with
a
check
if
the
value
of
the
counter
is
greater
or
equal
to
zero,
if
you
have
lots
of
documents
being
executed
concurrently
as
they
are
being
executed
in
different
data
centers,
we
can
execute
more
decrements.
Then
then,
then
we
can
okay.
So
this
is
the
bounded
counter.
C
So
we
had
a
couple
more
slides
about
something,
some
system
that
we
have
done,
that
is
Swift
thought
I
will
pass
over
this
slide,
but
just
in
one
minute
what
is
Swift?
Well,
we
have
built
a
database.
There
is
a
paper
online
that
you
can
read.
The
idea
is
that
we
in
Swiss
cloud
we
have
instead
of
having
just
the
full
database,
we've
moved
with
cached
part
of
the
database
in
the
client
machines.
C
Okay
and
allow
applications
to
executing
those
client
machines,
okay
and
I-
will
pass
all
the
slides
and
I
will
just
give
you
some
some
numbers
that
I
think
are
interesting,
so
we
have
done
this.
So
basically
that
is,
we
move
part
of
the
data
to
the
client,
okay
and,
as
we
move
part
of
dota
2
client
and
allow
applications
to
access
the
data
that
is
cached
in
the
okay.
C
In
these
two
lines,
the
the
pink
and
blue-
you
can
see
that
we
have
very
good
way
to
see
our
latency
is
almost
zero
because
most
of
the
operations
most
of
the
operations
go
is
acute
locally.
Okay,
because
data
will
be
on
cash.
Okay,
if
you
use
a
typical
approach
that
is
going
to
a
data
center,
the
weight
issue,
it
will
be
worse
because
we
have
the
time
to
send
our
request
to
data
center
and
to
get
the
reply
back
from
from
the
client.
C
Okay,
so
is,
however,
when
area
there
that
is
important
and
if
you
are
thinking
about
moving
your
data
to
the
client
side,
this
is
an
important
message
that
they
that
I
want
to
leave
here
today.
That
is,
after
you
have
a
first
cache,
miss
so
you're
in
the
client.
You
are
executing
operations
and
you
have
a
cache
miss
if
you
miss
you
have
to
go
to
the
server
or,
if
you
are
doing
a
complex
query,
where
you
don't
have
all
that
you
have
to
go
to
the
to
the
server
to
to
fetch
more
data.
C
C
Okay,
so
one
thing
that
that,
if
that
you
might
do,
if
you
are
trying
to
do
something
like
this
is
on
the
first
fashion
is
try
to
move
your
computation
to
the
server
the
rest
of
your
computation
to
the
server
and
get
the
ezq
temp
in
the
server.
So,
just
to
conclude,
let
me
let
me
conclude
fast,
so
things
that
we
have
learned
from
our
experience
and
from
experience
of
others
that
are
using
CDs
is
that
applications
require
multiple
types
of
C
oddities,
so
set
C.
R
DT
will
not
solve
all
their
problems.
C
C
It's
great,
so
it's
marking
is
shown.
So
when
you
see
this,
you
have
to
lower
your
expectation,
so
the
system
will
not
behave
like
everything
is
single,
a
single
server,
okay,
but
you
can
still
enforce
some
invariants
and
you
can
still
do
some
interesting
things,
so
you
can
do
multiple
keep
lights
with
Iowa
with
transactions,
something
that
we
have
in
in
sooth
loud
I.
Invite
you
to
read
the
paper,
so
you
might
have
first
causality.
Okay,
that
also
helps
with
some
invariants.
C
You
might
enforce
memory,
key
variance
as
I
shown
with
the
bonded
counter,
and
you
can
address
general
invariant
using
just
right
consistency,
so
that
is
the
the
work
that
that
mark
mention
it
before.
So,
with
this
I
finished,
my
my
talk
and
I
can
take
questions,
so
those
are
workers,
so
part
of
the
work
has
been
doing
to
those
persons
and
that's.
B
A
B
C
We
might
have
some
numbers
on
that,
but
that
depends
usually
on
the
on
the
number
on
the
on
whether
you
are
doing
proactive
distribution
of
Rights
or
not
so
in
our
prototype.
Basically,
what
we
do
is
how
do
when
the
system
is
is
running
the
replicas
try
to
exchange
rights
between
them
so
that
they
are
more
or
less
even
amongst
them.
So
in
that
case,
when
they
are
really
really
close
to
the
to
the
to
the
limit,
you
might
end
up
into
the
situation's
I
don't
have
those
numbers.
C
B
C
B
B
C
C
C
Strong
will
guarantee
that
you
will
not
overspend.
The
difference
is
what
was
implied
in
the
question.
Bye,
bye,
bye,
Russell.
That
is,
if
you
have,
if
you
have
a
strong
you
when
you
want
to
do
a
decrement
and
you
have
only
one
right
available,
so
imagine
the
counter
is
equal
to
one.
You
go
to
the
central
server
in
the
centre
of
servers
knows
how
it's
when
you
can
decrement
and
everything
is
fine.
So
when
you
have
the
bonnet
counters
and
for
example,
if
you
have
just
one
right
and
that's
right
can
be
in
any
replica.
C
B
A
B
B
A
B
A
You
could
argue
that
the
graph
database
will
be
very
similar
because
the
the
individual
element
is
just
you
know,
a
vertex
or
a
or
an
arc,
but
the
the
goal
here
is
to
be
able
to
especially
the
Swift
cloud
is
to
be
able
to
handle
very
large
databases,
but
only
replicate
the
the
small
part
that
you
are
you're
really
interested
in
partial
replication,
which
is
a
very
hard
problem.
Actually.
B
A
That
was
the
point
I
was
trying
to
make.
Is
that
if
you
want
to
maintain
its
invariance
okay
to
maintain
these
invariants,
you
have
to
have
the
precondition.
So
the
precondition
here
is
that
you
know
nobody
has
bid
on
this
thing.
Yet
right,
and
if
you
evaluate
that
you
know
locally
and
you
might,
you
might
read
the
wrong
value
for
your
precondition.
Okay,
so
in
these
cases
I
mean
this,
there
there's
a
proof
here,
I
mean
the
important
thing
is
that
is
so
intuitively.
A
Yes,
you
understand
that
you
know
maybe
I
need
to
do
something
here,
but
we
have
a
proof
that
there
is
only
two
choices
right
either,
but
there
it's
a
design
choice,
it's
a
design
choice
with
only
two
alternatives:
one
is
okay,
I
need
to
synchronize
and
it
cannot
be
a
co
duty.
Anymore
cannot
be
available
anymore
or
I
have
to
live
with
lower
expectations,
so
I
have
to
live
with
the
fact
that
two
people
could
bid
at
the
same
time
for
the
same
thing.