►
Description
Originally recorded during the Lisbon Hack Week from May 21-25, 2018.
Current designs for CRDT counters do not scale, having a size linear with the number of both active and retired nodes (i.e., nodes that leave the system permanently after previously manipulating the value of the counter).
In this talk, Vitor presents a new counter design called Borrow-Counter, that provides a mechanism for the retirement of transient nodes, keeping the size of the counter linear with the number of active nodes.
You can find Vitor at https://vitorenes.org/ or on GitHub and Twitter @vitorenesduarte
A
Hi,
so
my
name
is
Rita
I'm,
also
from
us
lab
as
Ali
and
I'll
talk
about
this
identity
explosion
problem
that
we
have
in
state-based
our
duties,
and
this
is
a
joint
work
with
Carlos
Baqir
al-sadr
in
journalism,
which
is
from
Nava.
The
other
two
auditors
are
from
as
love,
so
maybe
it's
not
even
metal
motivates
why
we
actually
do
that
replication
and
then
I'll
talk
about
this
problem
that
we
have
in
security
is
identity
explosion
and
then
some
how
we
actually
builds
charity.
A
So
this
may
be
useful
for
people
that
are
now
hearing
about
see
our
duties
for
the
first
time,
and
then
we
use
these
techniques
to
build
the
borrow
counter
that
attempts
to
solve
that
problem.
So
ye
replicates
because
it
improves
the
fault,
tolerance
of
our
system.
We
can
still
reply
to
our
clients,
even
when
some
of
the
servers
are
down.
It
improves
the
performance
because
we
can
place
replicas
close
to
our
clients
and
we
just
serve
the
same
data
from
multiple
servers
at
the
same
time
and
we
have
an
increased
throughput.
A
But
now,
since
we
have
more
than
one
copy
of
the
same
data,
we
need
to
pick
which
kind
of
consistency
model
we
want
between
these
these
copies
and
we
have
strong
consistency,
which
is
very
successful.
We
decided
at
the
center,
but
once
we
moved
to
wide
area
networks,
our
clients
will
have
to
wait
a
lot
so
just
to
have
an
idea
using
Google
clouds.
The
round-trip
time
between
London
and
Mumbai
is
close
to
700
milliseconds.
A
So
this
means
that
if
we're
running
something
like
pax
is
early,
that
is
in
London,
we
need
to
contact
a
replica
in
Mumbai,
because
it's
part
of
our
majority,
that's
close
to
us
and
the
lower
bound
on
consistency
is
one
roundtrip.
Our
client
will
wait
at
least
700
milliseconds,
plus
everything
else
we're
doing
in
our
stack.
The
alternative
is
we
just
reply
right
away
to
our
clients
and
we
have
eventual
consistency.
We
diverge.
We
have
possible
conflicts.
So
how
does
that
work?
Imagine
we
have
three
replicas.
A
They
are
replicating
a
set
empty
set
from
the
starts.
B
adds
an
element,
X
I
know
it
sends
something
to
see,
seen:
houses
X
and
now.
Concurrently,
you
have
an
addition
of
X
and
the
removal
of
X,
so
this
is
where
so.
This
is
what
we
call
a
conflict,
and
here
we
need
to
decide
what
will
happen
to
our
States
and
the
possible
solution.
Series
we
say
X's
in
the
sets
or
X
is
not
in
the
set,
and
these
are
to
conflict
resolutions
that
we
have
in
C
our
duties.
A
A
Let's
imagine
we
have
a
client
and
a
server
server
has
the
counter
at
0
and
the
client
issues
an
increment
to
a
serving.
Since
this
is
a
message
now,
the
server
takes
its
state,
which
is
0
and
increment,
is
to
1
later
on.
The
client.
Does
another
increment
sends
another
message,
and
now
the
service
state
is
2.
So
the
question
is
what
if
M
1
is
lost
in
here,
we
can
see
that
the
final
value
of
the
country
will
be
1
right,
because
when
the
server
receives
M
2,
it
will
actually
have
the
value
0.
A
A
So
you
see
like,
if
it's
lost,
should
the
clients
try
again
or
try
again,
and
in
that
case
it
doesn't
know
what
the
final
value
of
the
counter
will
be.
So
any
stock
will
try
to
solve
that,
and
the
first
step
is
to
actually
keep
State
on
the
client.
So
the
client
also
has
the
counter
state
which
starts
at
zero.
A
So,
what's
the
problem
here
probably
here
is
that
now,
if
we
have
two
these
two
clients-
and
they
do
this-
we
can
stress
to
the
maximum
of
the
the
two,
because
we'll
lose
one
of
the
increments
rights
and
what
CRD
T's
do
is
to
have
a
counter
per
per
replica.
So
when
clients
B
doesn't
increment,
it
comments
its
own
entry
of
the
map,
the
same
for
clients
a
and
now
the
server
just
keeps
all
these
entries
and
the
trick
with
the
max.
We
also
do
it
so
like
client.
A
I
can
still
send
these
again,
and
it
will
do
the
max
here
and
we're
fine.
We
still
handle
like
these
retry
problems
now.
The
problem
with
this
is
that
this
doesn't
scale,
because
we
have
to
keep
an
entry
per
all
the
clients
in
the
system
and
how
our
observation
was
that
we
need
to
do
this,
even
if
some
of
these
nodes
live.
A
So
what
we're
going
to
do
here
is
is
to
distinguish
nodes
that
are
permanent,
that
are
always
in
the
system.
From
knows
it's
joining
live
and
these
transient
nodes
will
borrow
the
identity
of
a
permanent
not
to
increment
the
counter,
and
when
they
decide
to
leave,
we
have
a
way
to
do
a
safe
retirement
of
these
nodes
and
incorporate
the
increments
in
the
permanent
nodes.
A
Okay,
so
we've
seen
notation
for
maps
sets
it's
similar
and
so
I'll
use
these
okay.
So
what's
this
I,
this
I
is
replica
identifiers
and
in
the
growing
country,
so
before
we're
mapping
replica
identifiers
to
to
natural
numbers
here
in
the
despair
I'm
having
a
replica
identifier
and
the
natural
number
and
I'll
just
represent
it
like
that,
and
if
I
have
a
boolean
I'll
just
so
we
go
from
true
to
false,
and
that
means
like
from
underline
to
over
line.
You
can
think
of
it
as
active
to
inactive.
A
So
it's
like
an
entry
that
is
active
to
inactive
and
I'll
talk
about
dots,
which
are
unique
identifiers
and
for
now
we'll
we're
going
to
use
like
geometric
figures
and
the
notation
music
for
that
is
this
bolt
circle?
Okay,
so
this
is
the
same
example.
We've
seen
just
in
another
perspective,
we
have
increments.
A
So
one
datatype
edwin
set
with
a
very
old
design
where
we
are
mapping
elements
to
a
set
and
they
set
as
dot.
That
is
tagged
with
a
boolean
which
will
say
if
the
dot
is
active
or
not
so
we
had
x
and
we
create
a
unique
identifier.
This
triangle,
which
is
active
for
now,
and
if
we
want
to
remove
you,
just
mark
it
as
inactive,
we
do
the
same
thing
for
another
element.
We
create
a
new
identifier,
it's
active
now
now
it's
inactive.
A
So
now,
when
we
create,
we
add
an
element,
we
map
it
to
the
to
the
unique
identifier,
but
we
put
it
on
the
rights.
So
when
we
want
to
remove,
we
can
just
forget
it,
and
this
is
because
see
seeds
on
the
right.
We
know
it
was
on
the
left
and
it
was
removed
and
this
I've
learned
last
week
this
was
called
the
nono
streak
for
some
time
he's
here
you
want,
if
you
want
to
ask
him
about
how
this
works
or
in
more
detail.
A
A
These
dots
are
not
geometric
figures,
as
you
might
have
guessed,
they
are
actually
a
pair
of
a
replica
identifier
and
the
sequence
number,
and
if
we
have
causal
dissemination,
this
causal
context
can
be
which
I'll
use
CC
from
knowing
can
be
encoded
as
a
vector
and
if
you
don't
have
there
are
still
possible
in
colleges
that
you
can
do
but
I'll
keep
the
naive
notation.
So
I'll
just
keep
sorry
I'll
just
keep
doing
this,
so
another
data
type
multi-value
register.
A
So
you
see
now
we
have
dots,
mapped
to
the
value
of
the
register
and
we
have
this
causal
context.
There
will
always
have
this
causal
context
because
it
allows
us
to
district
where
we
can
forget
things
so
replicate,
writes
Lisbon,
it
creates
a
dot,
and
that
is
also
in
the
causal
context.
So
when
replicate
writes
another
thing
in
the
register,
you
see
it
just
forgot
about
Lisbon.
Now
it
has
a
new
dot
map
to
ello
and
concurrently.
You
have
be
writing
world,
and
this
is
what
you
get
in
a
multi-value
register.
A
If
you
have
concurrent
rights
in
the
register
when
you
emerge
them,
you're
going
to
keep
both-
and
this
is
problematic-
because
these
not
what
users
are
expecting
so
so
they
write
something
and
when
they
read
they're,
expecting
to
read
a
single
value,
not
like
multiple
values-
and
this
is
actually
not
related
with
the
talk
but
I'll
keep
just
going
because
I
know
so
solution.
You
use
the
left,
writer
wins.
And
now,
when
you
write
you,
you
supply
a
timestamp
as
a
user,
so
you
say:
I'm
writing
Lisbon
at
11:02.
A
I'm
writing.
A
lo
at
11:04
can
currently
be
rights
with
11:30.
You
know
in
emerge,
since
this
timestamp
is
bigger
than
that
one.
You
you
mean
world
wins,
and
the
problem
here
is
that
we
just
lost
one
of
the
rights.
So
a
is
not
happy
now
mm-hm
any
systems.
Well,
it
assumed
single,
unique
timestamps
because,
like
if
hello
and
world
were
written
with
the
same
timestamp,
what
should
we
do
here
and
also
the
problem?
A
A
So
so
now
we
know
enough
to
build
this
burrow
cancer
and
again
the
idea
is
that
transit
nodes
will
ask
something
to
permanent
notes,
so
the
identity
in
the
form
of
the
dots
and
the
transit
nodes
will
increment
the
counter
using
these
dots-
and
you
can
maybe
already
imagine
that
sister
using
these
dots
and
we
have
the
causal
context,
we
can
do
this
trick.
Where
we'll
be
able
to
forget
that
these
transit
know
that
we're
existed.
A
So
what
will
build
it
from
block
small
steps
and,
in
the
end,
we'll
get
the
final
design
so
initially
going
to
have
a
dot
map
to
the
value
of
the
counter
and
the
causal
context?
And
now
we
have
a
so
start
sweet
the
counter
at
zero,
and
it's
just
increments.
Okay.
So
this
this
slides
just
means
that
this
is
where
we'll
keep
the
value
of
the
counter.
Sorry
in
this
end,
but
now
we
also
need
to
track
who
owns,
which
dot.
So
it's
replica
should
say
this
is
the
that
I
have.
A
This
is
that
I
can
use
to
increment
the
counter.
So
before
we
had
just
a
single
map
from
dots
to
Naturals.
Now
we're
going
to
map
identifiers
to
this
map,
so
this
means
that
if
some
replicas
an
entry
to
live
some
dots
here
two
years
and
in
this
in
this
example-
we
have
to
note-
is
a
permanent
node
and
3t
is
transient.
A
Okay,
so
we're
creating
a
dot.
So
we
can
increment
a
a
that
is
permanent.
It
creates
a
dot
for
itself.
You
later
on
tt-that
joined
the
system
will
ask
okay.
I
want
to
increment
a
counter.
Give
me
a
dots,
so
we
can
see
here.
This
is
the
dot
of
T,
which
is
beta.
So
now,
if
T
wants
to
increment
our
value
by
17,
you
just
increments
that
position,
and
now
you
have
a
problem
which
is
T
wants
to
live,
but
we
are
no
way
to
tell
that
in
the
States
right.
A
So
the
idea
is
that
we're
going
to
make
tea
make
a
promise
that
it
will
never
increment
the
counter
and
we're
going
to
use
that
as
a
way
to
safely
removed
tea
from
the
tea
from
that
map,
and
so
transit
notes
should
mark
dots
as
inactive
and
for
that.
So
what
changed
here
is
that
now
we
have
this
boolean
here
that
will
say
these,
the
dots
active
or
not-
and
this
is
the
final
design
of
the
bar
country.
So
same
example,
and
now
you
see
that
the
dot
is
active.
A
So
it's
like
the
underline
active
same
example.
Now
it
increments,
we
have
this
dot
active
and
now
to
retire.
We
simply
marketers
inactive.
And
now,
when
ace
is
this,
it
will
understand
that
tea
wants
to
leave
the
system
it
doesn't
have.
All
these
dots
are
inactive,
so
I
can
just
transfer
all
those
increments.
To
me.
A
A
Okay,
so
that's
what
we
covered.
We
have
a
design
for
counters
that
it
still
works
over
these
unreliable
networks
where
think
and
file,
and
we
may
need
to
retry.
We
focus
on
an
increment
only
counters,
but
these
works.
If
you
want
to
just
decrement,
it's
a
trivial
exercise
to
add
that
and
what
we
didn't
cover.
So
this
is
like
some
work
by
a
slab.
A
I'm
copying,
no,
no
slides.
So,
okay,
there
are
other
CIT
variants,
Delta
State
base.
This
paper
shows
some
problems
that
we
found
while
implementing
the
pure
operation
base.
So
this
composition
is
when
we
have
several
see
our
duties
and
we
want
to
put
them
once
inside.
The
others
like
put
Cantor's
inside
maps,
and
these
are
two
papers
that
show
possible
problems
and
potential
solutions
for
that
and
I
didn't
find
the
name
for
this
part,
but
so
these
scalable
eventual
consistency
counters
is
work
that
tries
to
solve
this
exact
problem.
A
B
B
A
B
A
That's
an
interesting
way
to
look
for
it,
so
this
is
just
working
progress,
so
just
presenting
one
of
the
problems
that
I
think
there
exists
currently
in
state
authorities
that
your
state
will
live
will
be
polluted
by
all
the
replicas
that
ever
did
something
in
this
state.
So
this
may
be
a
way
to
start
looking
at
this
and
try
to
do
stuff
leave
the
system
without
having
a
permanent
impact
forever.
I.