►
Description
Consistency is hard and coordination is expensive. As we move into the world of connected 'Internet of Things' style applications, or large-scale mobile applications, devices have less power, periods of limited connectivity, and operate over unreliable asynchronous networks. This poses a problem with shared state: how do we handle concurrent operations over shared state, while clients are offline, and ensure that values converge to a desirable result without making the system unavailable?
We look at a new programming model, called Lasp. This programming model combines distributed convergent data structures with a dataflow execution model designed for distribution over large-scale applications. This model supports arbitrary placement of processing node: this enables the user to author applications that can be distributed across data centers and pushed to the edge. In this talk, we will focus on the design of the language and show a series of sample applications.
Christopher Meiklejohn
MACHINE ZONE, INC.
@cmeik
Christopher Meiklejohn is a Senior Software Engineer with Machine Zone, Inc. working on distributed systems. Previously, Christopher worked at Basho Technologies, Inc. on the distributed key-value store, Riak. In his spare time, Christopher develops a programming language for distributed computation, called Lasp. Christopher is starting his Ph.D. studies at the Université catholique de Louvain in Belgium in 2016.
A
Hi
I've
got
a
tape
I'd
like
to
play,
consider
a
distributed
register,
so
we're
gonna
have
two
copies
of
this:
distributed
register
replica
a
and
replica
B.
So
what
we're
gonna
do
is
we
can
do
two
operations
on
this
register.
We
can
set
the
value
and
we
can
retrieve
the
value
so
here
we're
going
to
set
the
value
of
one
and
we're
gonna
asynchronously,
send
the
result
to
replica
B
and
imagine
this
is
running
in
a
distributed
system.
A
So
concurrently,
we
can
also
set
the
register
to
two
ever
applique
after
the
original
operation
is
done
and
then
set
to
a
replica
set
to
see
on
replica
B.
So
once
we
deliver
these
messages
in
the
system,
how
can
we
know
what
the
value
is?
Gonna
be
right?
How
do
we
know
that
replica,
a
and
replica
B
will
choose
the
same
value,
and
how
do
we
know
what
that
value
is
going
to
be
from
the
from
the
point
of
programming
this
model?
A
So
traditionally,
we
kind
of
use
synchronization
in
systems
to
enforce
an
order,
and
what
this
allows
us
to
do
is
reason
about
what
the
value
will
be
given
certain
inputs
right.
So,
given
that
we
take
certain
actions,
we
can
reason
about
what
the
result
of
those
actions
is
going
to
be,
so
this
assists
in
making
programming
easier.
A
This
also
eliminates
accidental
non
determinism
in
the
system.
So
if
you
have
a
concurrent
system
and
you
can
have
different
scheduler
interleavings
and
you're-
not
locking
data
structures
correctly,
you
can
have
the
value
under
subset
under
multiple
executions
of
this,
for
the
same
input,
return
different
values
for
the
output
and
kind
of
traditionally,
we've
had
techniques
for
doing
this,
such
as
locking
mutex,
is
semaphores
monitors,
and
you
know
all
of
the
distributed
kind
of
extensions
of
this
work
right.
A
So
synchronization
is
expensive
because
we
have
to
spend
time
we
have
to
spend
time
to
order
things.
We
have
to
spend
time
to
wait
for
things,
and
you
know
in
some
systems.
This
is
fine.
If
we're
on
a
single
machine,
it's
it's
okay,
I
mean
it's
not
great,
we'd
like
to
not
have
it,
but
there
are
kind
of
two
new
real
trendy
classes
of
applications
that
make
this
problem
exacerbated
right.
So
the
first
is
Internet
of
Things.
A
So
if
we,
if
we
think
about
what
Internet
of
Things
really
means,
we
have
devices
that
are
low-power,
they
have
limited
memory
to
operate
with
and
they
usually
have
limited
connectivity
and
the
reason
they
have
limited
connectivity
is
because
it's
really
expensive
in
terms
of
power,
to
run
the
antenna
that
a
lot
of
these
devices
use.
If
these
devices
happen
to
operate
over
shared,
stay
and
computing
aggregates,
they
can
make
concurrent
modifications
to
shared
aggregates
and
then
come
online,
and
we
have
a
problem
of
divergence.
A
Similarly,
one
of
the
research
partners
in
the
research
group
I'm
working
in
is
that
Rovio
entertainment,
so
mobile
gaming
is
another
area
where
this
is
really
difficult.
For
instance,
Angry
Birds
has
leaderboards,
has
profiles
and
Rovio
wants
the
ability
that
people
can
continue
to
play
the
game
while
they're
offline,
like
if
you're
in
an
airplane-
and
you
know
when
you
have
this
when
you
have
this
you're,
going
to
be
modifying
like
a
leaderboard
with
your
current
scores,
you're
going
to
be
updating,
you
know
potential
your
profile,
maybe
you
change
your
photo.
A
Maybe
you
change
your
name
and
then,
if
there
are
multiple
people
playing
out
of
the
same
account,
you
have
the
problem
of
reconciling
those
concurrent
changes
that
happen.
While
clients
were
offline
and
with
things
like
leaderboards,
even
when
the
state
is
just
you
know,
coordinated
its
its
state
that
we
all
kind
of
contribute
to.
We
also
have
the
problem
of
saying
well.
How
do
I
merge
this
into
this
global
kind
of
leaderboard
aggregate?
A
So
synchronization
is
expensive,
so
I
mean
we
want
to
have
our
cake
and
eat
it
too
right.
We
want
systems
that
don't
synchronize
at
all
and
I'm
sure
you've
seen
a
bunch
of
talks
at
this
conference
already
or
any
of
the
previous
years
that
talk
about
how
we
want
to
reduce
synchronization
whoa.
No
reduce
coordination
and
Peter
Bayliss
gave
a
great
talk
yesterday
about
that,
but
but
we
also
want
to
use
shared
state
right,
because
we
like
this,
we
want
to
have
concurrent
edits.
We
don't
have
to
route
it.
A
So
the
idea
that
we're
working
on
for
our
research
is
trying
to
start
from
the
point
of
zero
synchronization.
Can
we
start
with
no
synchronization
at
all
in
the
programming
model
and
then
only
apply
a
synchronization
where
it's
necessary,
so
instead
of
you
know,
instead
of
building
a
application
ecosystem
around
a
strongly
coordinated
system
such
as
zookeeper?
Why
don't
we
design
systems
that
start
with
no
coordination
and
only
use
the
coordination
mechanisms
when
we
need
to
enforce
something
a
global
system
invariant?
A
So
the
goal
of
the
research
that
we're
doing
and
that
we've
done
over
the
past
three
years
and
are
continuing
this
year
into
next
is
we
want
to
explore
the
limits.
If
we
want
to
see,
can
we
design
a
computational
model
that
allows
us
to
write
coordination,
free
computations
and
make
sure
that
these
computations
are
freaking
from
concurrency
anomalies
when
I,
say
concurrency
anomalies,
I
mean
things
like
the
Amazon
dynamo
show
up
in
cart,
where
items
can
come
back
because
we
use
a
simple
merge.
Union
function
across
like
divergent
copies
of
a
cart.
A
A
We
have
a
coupling
as
an
infrastructure
property
and
we're
not
talking
about
data
centers,
specifically
we're
talking
about
like
data
center
kind
of
latency
guarantees,
moving
to
open,
Internet
kind
of
guarantees,
as
we
as
we
move
outward
so
things
like
MapReduce
kind
of
fit
into
the
weak
sharing
model
and
the
strong
the
strong
coupling
model
right.
Mapreduce
is
so
it
is
possible
to
do
MapReduce
across
the
world.
I.
Imagine
you
can
do
it,
but,
but
usually
you
want
to
run
it
inside
on
a
data
center
right.
You
want
the
latency
requirements.
A
You
need
a
strongly
consistent
kind
of
coordination.
Membership
service
to
you
know
make
the
MapReduce
happen,
and
typically
you
only
share
state
at
the
reduced
phase
right.
So
the
map
is
embarrassingly
parallel
in
terms
of
study
at
home.
I
mean
this
is
really
like
super
embarrassingly
parallel
right,
because
we
don't
share
any
data.
You
kind
of
contact
the
service
every
once
in
a
while
to
check
out
a
block.
You
compute
that
block
you
send
it
back.
A
If
people
compute
multiple
blocks,
they
don't
care
because
that's
just
more
information,
so
study
at
home
is
kind
of
like
really
really
weak
on
the
coupling
property.
Is
this
open
Internet
idea
right
and
then,
if
we
think
about
things,
I
have
a
strong
sharing
property
kind
of
tied
to
this
model?
It's
things
like
Twitter
right,
so
I,
don't
know
the
deets
of
how
Twitter
is
implemented,
but
I.
Imagine
that
timelines
are
kind
of
objects
that
that
are
contended
for
that.
We
have
concurrent
operations
on
right.
A
Your
friends
are
going
to
tweet
and
they're
gonna
appear
in
your
timeline,
so
we're
gonna
have
a
single
kind
of
source
of
truth
of
this
object
and
we're
going
to
concurrently
write
to
this
object.
So
this
is
an
idea
of
strong
sharing.
So
in
a
graph
like
this
that
you
would
see
in
an
academic
talk.
Where
do
we
want
to
go?
Well,
we
obviously
always
want
to
go
into
the
upper
right
hand
quadrant,
because
that's
that's
the
area
that
usually
never
has
anything
in
it.
A
So-
and
this
is
the
area
where
we
got
to
have
a
weak
coupling
to
the
infrastructure,
where
we
don't
rely
on
a
particular
distribution
model
or
latency
requirements,
and
we
can
tolerate
things
being
offline
and
we
want
to
move
towards
the
strong
sharing
model.
So
we
can
share
a
lot
of
data
between
a
lot
of
different
clients
in
the
system.
A
So
we'll
briefly
kind
of
talk
about
fundamentals
of
distributed.
Computation
I'll
keep
this
short
because
there's
so
many
distributed
computing
talks
here.
That
probably
reiterate
a
lot
of
this.
So
when
we
look
at
concurrent
programming
concurrent
programming
had
a
problem
of
consistency
right,
we
have
to
reason
about
what
can
be
seen
by
what
threads
in
the
system
and
the
ideas
of
like
how
we
maintain
caches
and
things
like
this.
A
But
when
we
move
to
a
distributed
programming,
we
introduced
the
problem
of
partial
failure
right,
so
we're
gonna,
we're
gonna
write
to
a
bunch
of
replicas
and
some
of
them
are
gonna
succeed
and
some
of
them
are
gonna
fail
and
then
we're
kind
of
like
okay.
Well,
how
do
I
reason
about
if
I
go
to
contact
the
system
again
and
get
a
value
that
I
wrote?
Will
it
actually
be
there
right?
A
So
it's
really
hard
to
deal
with
partial
failure
and,
up
until
this
point
and
still
today,
a
lot
of
modern
databases
do
this
today
we
have
distribute,
we
do
distributed
computing,
assuming
the
illusion
of
a
single
system,
and
this
is
something
that
you
see
in
transactions.
Right
transactions
are
an
idea
to
address
this,
and
the
idea
of
the
system
saying
the
single
system
image
is
that
if
I
have
a
distributed,
database
and
I
write
a
value
to
one
of
the
replicas
and
then,
for
instance,
Tom
goes
to
read
that
value
he'll.
A
A
So
if
you
attended
Katie's
talk
yesterday,
she
kind
of
talked
about
this
idea
of
consistency
models,
so
consistency
models
are
in
distributed,
computing,
a
contract
between
an
application,
developer
and
a
system,
and
what
a
consistency
model
says.
Is
that
hey?
If
you
follow
these
rules,
I
guarantee
that
you'll
see
these
events
in
a
particular
order
and
some
consistency
models?
Don't
make
a
guarantee
right?
They
say
we
don't
know
when
you'll
see
the
events,
you'll
eventually
see
them
in
an
overt
order,
and
that's
our
favorite
consistency
model
right.
A
So
these
consistency
model
things
just
on
this
spectrum
right,
it's
weird
they're,
like
the
you
know,
the
graph
is
kind
of
like.
If
you
you
know
it's
like
all
over
the
place
and
all
of
these
things
and
you're
a
blonde.
You
know
snapshot
isolation
and
non-monotonic
snapshot,
isolation,
causal
cross
and
causal,
and
you
have
all
of
these
crazy
consistency
models
and
they
kind
of
all
exist
on
a
spectrum,
they're
kind
of
partially
ordered,
I,
guess,
right
and
and
to
get
a
stronger
consistency
model.
A
A
So
what
we
want
to
think
about
is
that
a
consistency
model
is
analogous
to
a
programming
paradigm,
because
it's
a
contract,
if
you
think
of
a
programming
paradigm,
like
you,
know,
functional
programming
and
dataflow
programming.
This
is
a
contract
that
says
well
giving
you
program
and
you
follow
these
particular
rules.
You
will
see
these
particular
types
of
outcomes
right,
so
it's
it's
like
contract
that
the
application
developer
makes
with
the
underlying
system
that
they're
that
they're
building
their
application
on
top
of
so
so
we'll
kind
of
step
back
and
say
all
right.
A
Well,
why
is
synchronization
undesirable,
so
it's
kind
of
intuitive
that
you
don't
want
to
do
this,
but
what
kind
of
you
know
walk
through
it
anyway?
So
we
have.
This
idea
of,
like
physical
time
is
really
hard.
So
if
you
went
to
John
Moores
talk
yesterday,
he
talked
about
the
problem
of
you
know:
synchronizing,
computers
with
NTP.
You
know
how
it
certain
interval
computers
gives
up
some
computers
like
just
won't
even
synchronize.
We
talked
about
the
problem
of
time
stamps
when
they're
used
for
deletions
and
if
you
delete
something
in
the
future.
A
A
The
first
one
is
kind
of
mutable
state
and
sequential
systems.
So,
if
you
think
of
sequential
systems-
and
you
have
functions-
and
these
functions
use
mutable
state-
these
functions
are
gonna,
take
different
values
over
time.
So
that's
kind
of
a
difficult
thing
to
think
about
right.
We
don't
have
these
nice
properties
of
referential
transparency
and
things
like
that
that
we
really
like
with
concurrent
systems.
Again
we
have
non
determinism,
so
different,
scheduler
interleavings.
A
When
you're
doing
multi-threaded
programming,
we
usually
use
locks
to
enforce
an
order
so
that
we
can
think
about
the
system
and
we
we
know
that
we
can
execute
it
multiple
times
and
get
the
same
result.
It's
the
worst
thing
is
to
run
a
computer
program.
You
know
given
two
values:
the
same
values
three
times
in
a
row
and
get
three
different
answers:
that's
not
really
a
fund,
a
job
to
have,
and
finally,
in
distributed
systems,
we
have
all
these
problems
on
network
latency
right.
How
do
we
do
failure?
Detection
I
mean
failure.
A
Detection
is
a
fundamental
problem
because
it's
very
hard
to
do
in
a
safe
manner.
How
do
we
coordinate
right?
How
do
we
ensure
that
we
see
events
in
a
particular
order?
So
a
lot
of
this
is
we
have
to
deal
with
time
because
it
takes
time
for
messages
to
go
across
the
network,
but
you
know
ultimately,
physical
time
is
unavoidable
because
it's
kind
of
like
a
real
thing
right
yeah
when
you
sit
down
at
a
computer
and
you
and
you
punch,
like
you-
know,
numbers
into
this
little.
A
A
So
physical
time
is
unavoidable,
it's
essential,
so
we'll
digress
for
a
minute
and
and
talk
about
the
parable
of
the
card,
so
we
think
about
a
car
and
how
a
car
drives
down
a
highway,
and
so
as
a
car
drives
down
the
highway,
it
uses
the
tires
grip.
The
road
right,
the
tires
grip.
The
road
in
this
creates
friction,
and
this
allows
the
car
to
propel
itself
forward,
and
these
friction
points
that
the
car
makes
with
the
road
are
very
small
right,
like
the
car
has
a
massive
surface
space.
A
A
So
the
motor
really
relies
on
it
being
as
frictionless
as
possible,
and
we
all
know
that
you
know
when
there's
a
lot
of
friction
inside
of
a
motor
lots
of
bad
things
happen.
Your
system
slows
down
your
system
stops
functioning
correctly,
and
these
are
all
things
that
cause
the
system
to
be
very
difficult
to
work
with,
so
we're
gonna
kind
of
think
about
physical
time.
A
So
if
we
look
at
this
box
here,
this
box
is
a
is
a
data
flow
graph?
So
just
imagine
it's
some
general
data
flow
composition,
computation
happening
inside
the
box
and
what
we
want
to
do
is
we
want
to
push
physical
time
to
those
interaction
points
right
as
the
car
interacts
with
the
physical
world
like
the
ground
and
the
highway
at
these.
At
these
funding
points
we
want
to
push
time
out.
We
don't
want
to
have
time
inside
that
box.
A
We
don't
want
to
have
physical
time
inside
the
box,
but
it's
okay
to
have
a
notion
of
logical
time
inside
the
box,
and
we
do
this.
We
do
this
all
the
time
if
you
saw
John's
talkie,
he
talked
about
you
know
let
the
use
of
Lamport
clocks-
and
we
have.
We
have
all
of
these
nice
causal
tracking
mechanisms
that
allow
us
to
reason
about
how
events
are
propagating
in
the
system.
But
we
don't
do
any
of
this
kind
of
based
on
physical
time.
A
A
So
going
back
to
the
second
slide,
where
we
said
well,
what
can
we
do
would
serve
zero
synchronization?
We
can't
really
do
much
if
we
have
a
bunch
of
computers
in
a
network
and
these
computer
are
not
actually
talking
to
each
other.
They,
you
know,
they're,
probably
not
working
together
and
they
can
probably
just
be
independent
single
systems,
so
we
can't
really
do
much
without
synchronization
at
all.
A
The
primary
requirement
for
this
model
is
fairly
weak.
It
only
requires
eventual
replicas
to
replicas
communication,
and
this
is
just
to
serve
the
purpose
of
delivering
all
of
the
messages
to
all
the
nodes
in
the
system,
and
this
can
be
done
transitively
right,
we
don't
actually
have
to
have
every
node
talk
to
every
node.
A
What's
nice
about
this.
Is
that
it's
order
insensitive,
so
it's
commutative.
We
can
receive
the
updates
in
any
order
and
it's
duplicate
and
sensitive.
We
can
have
replays
on
the
network,
it's
also
associative
as
well,
and
this
is
really
great
because
that's
a
really
good
match
for
unreliable
asynchronous
networks,
our
favorite
kind
of
networks,
so
strong
eventual
consistency
relies
on
monotonicity.
So
we're
gonna
briefly
talk
about
monotonicity.
We
don't
have
time
to
really
go
through.
You
know,
I
can't
pull
up
Wikipedia
and
walk
through
it
with
you
as
much
as
I'd
like
to.
A
But
you
know
we
will
kind
of
just
do
a
brief
demonstration
of
what
monotonicity
is.
So
if
we
go
back
to
our
original
example,
where
you
have
replicas
and
replicas
be,
we
do
our
set
operation,
we
asynchronously
propagate
the
result,
and
then
we
write
two
and
three
so
now
we
have
a
decision
to
make.
So
if
we're
operating
over
an
ordered
domain
of
which
the
natural
numbers
are
so,
let's
assume
we
only
set
natural
numbers,
this
domain
is
ordered.
Then
we
can
have
a
monotonic
function,
which
is
a
function.
A
That's
going
to
preserve
that
order
as
the
inputs
increase,
the
outputs
are
going
to
increase,
and
this
is
going
to
give
us
deterministic
execution
if
we
use
something
like
max,
which
is
a
monotonic
function
over
in
the
natural
numbers.
So
here
we
see
well
that
we
get
three,
because
three
is
the
greatest
value
that's
been
seen
and
what
I
can
do
is
I
can
take
any
node
in
this
graph.
I
can
completely
rearrange
it
and
I
will
still
get
the
same
results.
So
this
is
the
limiting
accidental
non
determinism
from
the
system.
A
So
if
you
went
to
the
CRT
t-talk,
that
was
earlier,
you've
probably
already
learned
about
strong
eventual
consistency,
so
I
apologize
for
any
duplication
in
content.
So
how
can
we
succeed?
Programming,
strong,
eventual
consistency,
so
what
kind
of
define
a
criteria
of
success-
and
this
will
be
the
outline
for
the
remainder
of
the
talk
and
and
then
we'll
kind
of
kind
of
look
at
what
applications
we
might
be
able
to
build
with
this.
So
start
here,
actually
so
well
well
begin
by
eliminating
accidental
non
determinism.
A
So
we've
seen
that
these
data
structures,
I
just
showed
you
and
these
monotonic
functions-
they're
really
helpful
in
removing
accidental
non
determinism
and
what
we
have
to
do
is
we
have
to.
If
we
want
to
make
this
general
one
a
general
purpose,
programming
model
we
have
to
eliminate,
we
have
to
have
the
ability
to
model
non
monotonicity
in
a
monotonic
way.
So
if
you
think
about
a
set,
a
set
isn't
monotonic,
because
it
that
you
can
remove
an
ad
from
because
over
time
it's
going
to
have
different.
A
You
know
if
we
count
the
elements
the
cardinality
is
changing
over
time,
so
we
have
to
have
a
way
to
model
that
in
a
monotonic
fashion.
So
we
can
reason
about
it
in
the
delivery
of
our
delivery
of
events
in
our
system,
we'd
like
to
retain
properties
of
functional
programming
that
allow
us
to
compose
those
objects,
because
it's
been
shown
that
converging
objects
don't
necessary
if
I
just
take
a
counter,
a
converging
counter
and
I
shove
it
in
the
convergent
set
that
will
not
converge
correctly.
A
So
we've
seen
that
some
of
these
things
are
difficult
to
do
so.
We
need
to
have
a
way
to
perform
composition
and
we
want
to
kind
of
move
as
closely
to
properties
that
resemble
confluence
and
referential.
Transparency
specifically
related
to
functional
programming
with
composition.
Sorry
and
finally,
we
need
a
way
to
distribute
all
this
stuff.
A
We
need
a
way
to
run
it
in
a
fault-tolerant
runtime
and
you
know,
be
resilient
to
failures
and
be
highly
available
and
all
of
the
the
things
that
make
it
very
practical
to
use
something
like
this
in
production,
so
we'll
start
by
eliminating
accidental
non
determinism.
So
you
probably
heard
about
CRT
T's
I.
Think
there's
been
a
talk
at
every
single
strange
loop
ever
on
see
already
teased
by
somebody.
A
There
was
another
one
this
year
and
CEO
duties
are
distributed:
data
structures
that
that
have
a
deterministic
resolution
under
concurrency,
so
under
concurrent
operations,
they
will
converge
to
a
particular
way
and
these
types
exist
with
many
different
properties.
We
have
different
varieties
of
all
these
things.
We
have
sets
counters
flags
which
are
like
excuse
me,
which
are
like
billions.
We
have
different
types
of
registers.
We
have
a
map
which
enables
composition
for
a
single
data
structure
and
there
are
graphs
and
these
data
structures
try
to
mimic
the
sequential
counterpart
as
much
as
possible.
A
However,
the
sequential
version
of
a
set
doesn't
have
a
concurrent
add/remove
operation
of
the
same
element,
so
a
lot
of
these
data
structures
they
take
biases,
they
say
well
under
addition
and
removal
of
the
same
item
at
different
nodes
in
the
network.
What
we'll
do
is
we'll
bias
towards
ads,
because
we
Intuit
that
you
know
users
will
only
remove
things
that
they've
seen
in
the
set.
So
if
you
follow
these
rules
again,
it's
back
to
decide.
You
have
a
contract
right.
A
If
you
follow
these
rules,
you
get
these
guarantees
and
what
CEO
duties
do
is
they
they
provide
strong
eventual
consistency
per
object
so
that
not
over
composition.
So
we're
going
to
walk
through
an
example
we're
going
to
assume
three
replicas
a
B
and
C
we're
gonna
model
our
set
as
a
set
of
triples.
So
this
is
a
set
of
a
triple
of
so
I'm
omitting,
the
outside
braces
to
make
it
more
readable.
A
Even
though
it's
not
super
readable
and
we
have
a
value,
we
have
a
set
of
unique
constants,
representing
unique
additions
like
a
nonce,
and
then
we
have
a
set
of
removals.
So
when
I
add
one
two
replicas
a
replica
a
generates,
this
random
lowercase,
a
constant
adds
one
to
this
set
and
then
propagate
asynchronously
propagates.
A
If
replica
C
then
adds
one,
it
has
an
observed
days
edition
yet
because
those
messages
are
taking
time
to
propagate,
so
replica
C
will
add
with
unique,
constant
B,
and
these
distinguishes
these
two
concurrent
additions
that
have
happened
in
the
system.
Now
she
wants
to
remove
one
from
the
set.
So
inside
the
circle
is
the
user
queryable
value
of
the
set?
A
So
if
C
wants
to
remove
one
from
the
set,
it
will
take
the
add
set,
which
is
a
set
of
B,
and
it
will
Union
it
with
the
remove
set
and
the
B
and
what
we
we've
created,
what
we
refer
to
as
a
tombstone
set
and
this
tombstone
stat
tracks
the
removals
of
items
in
the
network.
So
now,
when
we
deliver
all
of
these
messages,
eventually
we
guarantee
that
we
converge
to
the
right
result
and
the
way
we
do
this
is
it's
a
pairwise.
A
So
this
is
actually
modeled
as
a
monotonic
joint
semi-lattice,
but
it's
a
pairwise
mur
to
make
it
very
simple.
You
can
think
about
a
pairwise
merge
over
the
triples,
where
the
first
element
matches
by
unioning
descent
and
union
for
set
is
for
these
sets
because
they
only
ever
grow
is
monotonic
okay
to
determine.
If
the
element
is
in
the
set.
What
we
do
is
we
take
the
difference
between
the
ad
set
and
the
remove
set,
and
if
that
is
not
the
empty
set,
we
remove
it.
So
you
might
be
looking
at
this
saying
holy
crap.
A
That
is
a
lot
of
data.
You
were
storing
a
lot
of
data
for
a
set
that
at
one
time,
had
no
elements
in
it
and
yes,
you're
absolutely
correct.
These
sets
are
modeled.
You
know
these
are.
The
complexity
is
the
size
of
the
operations,
but
there
is
actually
a
very
efficient
modification
that
you
can
make
to
reduce
this,
to
be
just
the
size
of
the
active
elements
in
the
set
with
a
vector
that
represents
the
actors
in
the
system
and
how
many
times
they
perform
updates.
A
So
now
that
we
have
these
data
structures,
if
we
want
to
kind
of
retain
the
properties
of
functional
programming
like
these
ideas
of
confluence
and
referential
transparency,
we
need
to
have
a
model
that
allows
us
to
take
C
or
D
T's,
compose
them
and
get
out
a
C,
R
DT.
That's
got
this
convergence
property.
A
So
I
this
is
the
last
process
the
lattice
processing
works.
So
this
is
last
that
I,
don't
know
you
might
have
heard
of
this.
Is
the
stuff
I've
been
doing
for
the
past
year,
and
this
is
a
distributed.
Deterministic
dataflow
variant
for
eventual
consistency,
kind
of
programs,
eventually
consistent
programs,
and
what
we
mean
by
this
is
that
if
the
program
output
is
the
C
R
DT,
that
means
well
eventually
once
I
deliver
all
the
updates
and
even
if
nodes
get
partitioned
away
and
then
eventually
come
back
online
once
I
deliver
all
the
updates.
A
A
So
we
don't
have
a
mute
like
we
don't
have
normal,
like
you
know
like
a
integer,
so
there's
not
an
integer
and
what
we
do
is
we
have
a
way
of
doing
composition
so
that
all
of
that
internal
metadata
that
I
said
is
monotonically
growing.
That
I
showed
you
in
the
previous
example.
We
have
a
way
to
use
functional
composition
and
map
that
metadata
through
and
build
other
types
of
Co
duties
that
are
based
on
other
ones.
So
last
was
implemented
in
Erlang
and
and
Erlang
syntax
is
a
little
bit
debatable.
A
Sometimes
so
what
I'm
going
to
do
is
I
have
a
little
bit
of
pseudocode
here
you
see
types
are
specifically
encoded
in
the
calls,
because
erlangs
type
system
doesn't
really
allow
for
extension,
and
what
we
have
here
is
we
declare
a
set
of,
and
we
call
it
s1
we're
going
to
add
three
items
to
the
set.
So
we
add
items
one
two
and
three,
then
we
could
declare
a
second
set
and
then
we
can
take
the
first
set
apply
a
function
to
all
the
elements
in
the
set
and
then
generate
a
new
one.
A
So
this
s2
is
also
going
to
be
a
CR
DT
and
it
will
be
constantly
updated
from
s1
applying
this
map.
So
last
Palau
is
a
functional
and
set
theoretic
operations
on
sets.
We
specifically
in
the
paper
focus
on
sets,
but
the
implementation
has
some
stuff
for
counters
and
registers,
and
things
like
that,
but
the
paper
mainly
focuses
on
the
set
data
structure,
because
you
can
build
a
lot
of
things
in
terms
of
it.
We
allow
you
know.
A
We
have
operations
that
look
very
familiar
product
intersection,
Union,
filter
map,
fold,
things
like
that
and
what
these
operations
do
is
they
do
the
metadata
computation
they
transform
that
metadata
given
the
function.
So
if
you
have
a
map
and
you
map
into
another
set
and
I
change
the
value
of
the
element,
it
maps,
the
metadata
through
ensuring
you
have
a
CR
DT
on
the
other
side,
if
you
have
a
fold
and
you
fold
a
counter
a
set
into
a
counter,
it
will
perform
that
metadata
mapping.
A
So
we
have
this
idea
that
we
need
to
conserve
all
of
the
metadata
across
these
objects
to
guarantee
convergence.
This
is
like
kind
of
a
standard,
CRT
T
property-
that's
expressed
via
strong
eventual
consistency,
so
the
kind
of
the
way
last
works,
we'll
briefly
do
kind
of
a
high-level
overview
is
that
each
replica
in
the
system
is
a
monotonic
stream
of
states,
so
each
CR
dt
itself
only
ever
grows.
A
A
So,
in
addition
to
computing
the
Cartesian
product
of
the
sets
themselves,
we
produce
the
Cartesian
product
of
the
sets
metadata
to
ensure
that
if
I
take
two
of
those
objects,
those
will
both
converge
to
the
same
result
and
remember
this
is
tolerant
to
all
these
network
anomalies.
And
finally,
we
have
the
idea
of
inflationary
reads
and,
and
what
an
inflationary
read
is
is
it
ensures?
So
we
won't
go
into
the
details.
A
There's
a
good
conversation,
a
good
blog
post
by
Lindsey
Cooper
about
the
difference
between
inflation's
and
monotonicity,
but
what
it
allows
us
to
do
is
if
we're
reading
from
a
particular
replica
and
we've
seen
state
s,
and
then
we
see
state
s
Prime
and
then
our
connection
drops
and
we
go
back
to
a
different
replica
that
hasn't
got
the
s
Prime
update.
Yet
we
guarantee
that
we
won't
read
a
value
from
that
replica
until
it's
greater.
So
if
you're
familiar
with
distributed
databases,
this
is
related
to
a
session
guarantee
right.
A
So
we'll
look
at
a
quick
example
of
what
these
streams
look
like
to
just
demonstrate.
So
if
you
imagine,
we
have
two
clients
here
and
we
have
a
replica,
so
they
both
start
off
with
the
empty
set
and
we're
using
the
same
triple
notation
we
had
before.
If
one
is
added
with
a
in
the
add
set
and
then
that's
sent
to
replicas
a
and
concurrently
C
2
adds
with
B
and
sends
a
replica
a
replica,
a
does
not
choose
one
or
the
other,
it
merges
them
together
as
it
receives
them.
A
So
this
is
an
important
distinction
from
systems
that
use
something
like
glass
writer
winds,
where
we're
racing
to
see
which
value
we're
going
to
draw.
So
in
this
system
were
always
growing,
we're
always
moving
forward
and
then
see
one
can
continue
to
apply,
updates
to
its
local
state
and
send
them
to
replica
a
and
then
eventually
it
can
get
the
state
from
rep.
Okay,
if
it
likes
in
this
example,
this
stream
at
replica
is
monotonic.
This
is
always
growing
over
time.
It's
actually
inflationary
because
the
mutation
is
applied
and
the
resulting
state
is
always
greater.
A
So
if
we
want
to
build
a
system
to
compose
these,
we
do
this
with
this
idea
of
the
of
the
monotonic
process.
So
again,
we'll
go
back
to
we're
using
a
similar
example.
Replica
a
has
the
empty
set.
We
have
a
process
which
is
going
to
apply
our
map
function
and
then
F
of
ereve
is
just
going
to
be
the
value
with
the
map
applied
to
the
element,
so
we're
just
using
that
for
shorthand.
A
Here
we
do
this
with
state,
you
probably
say:
wow,
it's
really
efficient
to
keep
inefficient
to
keep
the
whole
state
around.
Yes,
it's
true
in
practice,
you
know,
semantically,
we
can
do
this
with
the
full
state,
but
in
practice
we
use
logical
clocks
to
model
this,
so
you
can
do
this
with
a
version
vector
and
then
finally,
the
state
changes
again
one
is
removed
from
the
set
the
functions
applied
and
the
map
function
produces
a
set
where
the
values
been
changed,
but
the
element
still
deleted.
A
A
So,
finally,
we'll
briefly
talk
about
some
work.
That's
in
progress
called
selective
hearing.
This
is
a
epidemic
broadcast
based
runtime
system
that
we've
developed.
So
if
you're
familiar
with
gossip
protocols,
this
is
a
we
build
on
the
gossip
protocol
work.
Gossip
protocols
allow
for
a
very
efficient
dissemination
of
information,
so
reliable
broadcast
under
failures
that
can
handle
a
very
large
amount
of
nodes.
We've
seen
some
protocols
do
ten
fifteen
twenty
five
thousand
nodes
in
evaluations
and
what
makes
this
matching
so
brilliant
is
that
broadcast
protocols
achieve
their
efficiency
through
weak
ordering.
A
So
this
is
why
it's
not
a
general-purpose
model
to
build
things
on,
but
that's
great,
because
we
don't
care
about
message
ordering,
though
our
entire
computational
model
builds
on
the
fact
that
messages
can
be
reordered
and
we
guarantee
that
we
converge
correctly.
And
finally,
the
reason
for
the
name
selective
hearing
is
that
we
want
nodes
to
be
able
to
selectively
kind
of
opt
into
computations.
So
if
I
have
a
program
that
requires
some
variable,
state
and
I
know
that
that
variable
state
is
on
these
five
nodes.
A
Then
I
can
express
kind
of
interest
in
that
variable.
So
it's
kind
of
a
runtime
that
resembles
a
publish/subscribe
system.
So
I've
shown
you
I've
shown
you
that
you
can
eliminate
accidental
non
determinism
through
CRT
peas.
We
can
find
a
way
to
compose
these
things
and
build
other
CRT
teas
and
finally,
we
can
efficiently
distribute
them
with
a
really
nice
runtime,
that's
efficient.
So
now
the
question
is
well:
can
we
actually
even
build
anything
than
any
of
this,
so
hopefully
so
we're
going
to
talk
about
a
mobile
game
platform?
So
imagine
angry
birds.
A
As
an
example,
advertisements
are
going
to
be
displayed
with
in-game,
clients
are
going
to
go
offline
and
people
are
going
to
continue
seeing
ads
in
the
game.
So
we
want
clients
to
be
continued
to
make
progress
still
record
the
ad
impressions,
and
we
want
to
do
this
completely
coordination
for
you
or
minimizing
coordination
as
much
as
possible.
So
this
is
what
the
data
flow
graph
looks
like
and
we'll
walk
through
it.
A
So,
let's
imagine
that
there's
a
notion
of
contracts
to
make
the
example
a
little
bit
more
difficult
and
contracts
are.
You
know
saying
that
an
ad
is
able
to
be
displayed
at
a
particular
time,
so
what
you'd
want
to
do
like
in
Ruby
on
Rails
or
a
web
framework
similar?
That's
similar
to
that
is
you
would
say
to
your
sequel
database.
Well,
hey
you
know,
computer
join
where
these
two
things
are
equivalent
where
the
keys
match.
So
in
data
flow.
We
can
kind
of
model.
A
This
with
you
know:
compute
computing,
a
Cartesian
product
and
then
doing
the
filter
and
then
only
getting
the
ads
that
are
active.
We
can
give
these
clients
all
out
too,
so
we
can
distribute
these
counters
out
to
the
clients.
The
clients
can
continue
to
increment
these
counters,
so
they
have
a
counter
that
represents
kind
of
a
global
counter,
and
then
they
diverge
from
that
and
then
they
periodically
send
their
counters
back
to
like
the
data
center
and
then
the
data
center
runs
a
process.
A
That's
doing
one
of
those
inflationary
reads,
it
says:
don't
let
me
don't
let
this
process
continue
running
until
the
advertisement
reaches
50,000.
So
all
these
clients
are
continuously
merging.
They're
stayed
in
the
counter,
is
growing,
slowly
monotonically
and
then,
when
we
hit
that
trigger
value,
we
remove
items
from
the
set.
The
set
is
modeled
monotonically
so
that
flushes
down
to
the
clients-
and
this
is
done
completely-
the
only
part
we
have
coordination
is
where
we
synchronize
with
the
server
to
send
our
states.
So
this
is
great.
The
advertisement
counter
is
completely
monotonic.
A
We
can
disable
contracts
and
advertisements
all
through
monotonicity,
all
with
monotonicity.
The
counter
itself
is
monotonic.
Obviously
it's
a
girl
on
the
counter
and
we
could
take
any
node
in
that
graph
and
put
it
on
anywhere
any
physical
machine,
because
the
data
structures
correctly
capture
the
concurrency
in
the
system
and
an
are
guaranteed
to
merge
correctly.
So
we
can
arbitrarily
distribute
this
graph.
That's
really
really
nice.
A
Let
me
put
it
all
on
the
same
machine
if
we
want,
and
finally,
if
we
think
of
the
system
as
having
a
global
truth,
if
we
had
an
outside
observer,
who
can
see
the
global
truth
of
what
the
counters
are,
we
can
measure
divergence
as
how
often
we
synchronize
and
put
our
results
into
the
global
result,
so
you
know
wrap
up,
I
think
behind.
So
what
do
I
like
about
this
model?
We
have
built
up
from
zero
synchronization.
We
didn't
build
a
system
where
we
had
to
remove
coordination.
A
So,
finally,
just
kind
of
talk
about
what's
next
briefly,
because
I'm
running
out
of
time,
metadata
can
grow
very
large.
We've
shown
that
we
have
mechanisms
for
reducing
the
metadata
in
the
system.
We
have
efficient
representations
of
sets
that
use
vectors
rather
than
storing
all
of
the
operations,
and
we
actually
have
a
unpublished
appendix
to
our
original
paper.
That
extends
us
to
a
bunch
of
other
different
optimized
data
types
that
that,
hopefully,
will
make
a
public
appearance.
Soon
I
Function
is
is
not
amazingly
general.
A
It
relies
on
the
binary
function,
applied
to
fold
to
be
associative,
commutative
idempotent
and
have
the
ability
to
be
inverted.
So
if
I
have
a
set
where
I've
removed
the
item
and
added
the
item
multiple
times,
I
need
to
and
I'm
folding
that
into
a
counter.
I
need
to
have
a
way
to
reflect
the
additions
of
the
count,
the
increments
of
the
counter
and
the
decrement
of
the
counter
in
a
in
a
way
where
I
conserve
the
metadata
between
the
two
objects
completely
and
finally,
what
can
we
derive
from
the
data
flow
graph?
A
So
can
we
do
things
where
we
see
that
hey
you're
running
this
map
on
this
node
and
this
filter
on
this
node?
Well,
we
can
just
combine
these
things
right
into
a
fold.
So
can
we
use
the
data
flow
graph
to
derive
distribution,
and
can
we
use
a
minimum
required
distribution
to
derive
an
optimized
data
flow
graph?
So
this
is
stuff
that
I'm
really
interested
in
but
have
not
even
begun
thinking
about,
but
seems
exciting,
so
to
kind
of
wrap
up?
What
have
we
learned?
A
Like
you
know,
you
have
to
be
tolerant
up
to
some
number
of
failures
and,
depending
on
how
you
replicate,
can
we
build
a
runtime
system
that
allows
us
to
do
very
efficient
scaling
of
this
programming
model
so
to
wrap
up
one
of
the
key
points.
Synchronization
is
expensive.
You
probably
all
know
this.
You
know
you're,
never
gonna
get
faster
than
the
critical
section
that
you're
locking
on
this
is
kind
of
straightforward
concurrent
programming.
A
lot
of
these
applications
are
not
possible.
It's
not
possible
to
synchronize,
always
so.
A
If
you're,
a
mobile
application,
clients
are
going
to
be
offline.
Occasionally
a
funny
anecdote
was
I
said
at
one
point:
you
know
you
call
your
friends
and
compute
a
round
of
consensus.
Tell
them
to
get
online
at
7:00
and
Paul.
Brill
said
back
to
me.
Well
now,
you've
just
pushed
the
consensus
problem
over
the
phone
and
finally,
you
know
some
things
require
synchronization
global
invariants
atomic
visibility.
So
we
have
a
bunch
of
papers.
A
You
can
check
them
out
if
you'd
like
we
tagged
a
release
0.01,
it
took
me
forever
to
get
this
Erling
packaging
thing
working.
Even
though
I
have
a
ton
of
experience
with
it.
Oh
well,
so
it
works.
You
can
download
this
package,
it's
a
it's,
a
not
comprehensive
implementation
or
everything
be
built,
but
it's
fully
executable
and
you
can
run
our
demo
program.
So
that's
kind
of
nice
and
finally
I'd
like
to
thank
the
European
Union.