Distributed Data Flow Language for Multi-Party Protocols
Distributed Data Flow Language
for Multi-Party Protocols
Krzysztof Ostrowski
†
, Ken Birman
†
, Danny Dolev
§
†
Cornell University,
§
Hebrew University
{krzys|ken}@cs.cornell.edu, dolev@cs.huji.ac.ilIntroduction
http://liveobjects.cs.cornell.edu
http://liveobjects.cs.cornell.edu
distributed
peer-to-peer
protocols
http://liveobjects.cs.cornell.edu
distributed
peer-to-peer
protocols
multicast
locking
replication
commit
http://liveobjects.cs.cornell.edu
distributed
peer-to-peer
protocols
multicast
locking
replication
commit
shared
content
http://liveobjects.cs.cornell.edu
distributed
peer-to-peer
protocols
multicast
locking
replication
commit
replicated
content
http://liveobjects.cs.cornell.edu
multicast
locking
replication
commit
replicated
content
distributed
peer-to-peer
protocols
synchronization,
coordination
http://liveobjects.cs.cornell.edu
http://liveobjects.cs.cornell.edu
http://liveobjects.cs.cornell.edu
http://liveobjects.cs.cornell.edu
http://liveobjects.cs.cornell.edu
basic
building
block
http://liveobjects.cs.cornell.edu
basic
building
block
http://liveobjects.cs.cornell.edu
basic
building
block
http://liveobjects.cs.cornell.edu
need
lots of
different
objects
(protocols)
http://liveobjects.cs.cornell.edu
need
lots of
different
objects
(protocols)
user-defined
objects
How to Implement New Objects?
custom
user-defined
object
custom
user-defined
object
Java / C# / C++
protocol
composition
Frameworks
(Ensemble,
BAST, Appia)
MACE,
P2, etc.
How to Implement New Objects?
custom
user-defined
object
Java / C# / C++
protocol
composition
Frameworks
(Ensemble,
BAST, Appia)
MACE,
P2, etc.
How to Implement New Objects?
custom
user-defined
object
Java / C# / C++
protocol
composition
Frameworks
(Ensemble,
BAST, Appia)
MACE,
P2, etc.
How to Implement New Objects?
higher-level logic
(making decisions)
Java / C# / C++
protocol
composition
Frameworks
(Ensemble,
BAST, Appia)
MACE,
P2, etc.
lower-level logic
(e.g., ACKs, timeouts,
building rings/trees,
internal bookkeeping)
intermingled,
tightly-coupled
How to Implement New Objects?
higher-level logic
(making decisions)
lower-level logic
(e.g., ACKs, timeouts,
building rings/trees,
internal bookkeeping)
intermingled,
tightly-coupled
How to Implement New Objects?
higher-level logic
(making decisions)
lower-level logic
(e.g., ACKs, timeouts,
building rings/trees,
internal bookkeeping)
intermingled,
tightly-coupled
How to Implement New Objects?
less
flexibility
harder to
write/debug
Java / C# / C++
protocol
composition
Frameworks
(Ensemble,
BAST, Appia)
MACE,
P2, etc.
error-
prone
less
sophisticated
How to Implement New Objects?
less
flexibility
harder to
write/debug
Java / C# / C++
protocol
composition
Frameworks
(Ensemble,
BAST, Appia)
MACE,
P2, etc.
error-
prone
less
sophisticated
How to Implement New Objects?
less
flexibility
harder to
write/debug
Java / C# / C++
protocol
composition
Frameworks
(Ensemble,
BAST, Appia)
MACE,
P2, etc.
error-
prone
less
sophisticated
How to Implement New Objects?
less
flexibility
harder to
write/debug
Java / C# / C++
protocol
composition
Frameworks
(Ensemble,
BAST, Appia)
MACE,
P2, etc.
error-
prone
less
sophisticated
How to Implement New Objects?
How to Implement New Objects?
lower-level logic
(e.g., ACKs, timeouts,
building rings/trees,
internal bookkeeping)
higher-level logic
(making decisions)
separation
of concerns
How to Implement New Objects?
separation
of concerns
programmer
compiler and
runtime
How to Implement New Objects?
separation
of concerns
programmer
compiler and
runtime
Our Approach:
Flows
Objects
Aggregation
Batching
Recursion
e
1
e
2
x
1
crashed
x
1
crashed
e
3
x
4
joined
x
4
joined
e
4
x
4
joined
e
5
x
4
joined
e
6
example: distributed locking protocol
example: distributed locking protocol
application
layer
example: distributed locking protocol
application
layer
protocol
layer
example: distributed locking protocol
application
layer
protocol
layer
example: distributed locking protocol
example: distributed locking protocol
example: distributed locking protocol
example: distributed locking protocol
example: distributed locking protocol
example: distributed locking protocol
example: distributed locking protocol
example: distributed locking protocol
example: distributed locking protocol
example: distributed locking protocol
example: distributed locking protocol
example: distributed locking protocol
example: distributed locking protocol
example: distributed locking protocol
example: distributed locking protocol
example: distributed locking protocol
example: distributed locking protocol
example: distributed locking protocol
example: distributed locking protocol
Our Approach:
Flows
Objects
Aggregation
Batching
Recursion
example: distributed locking protocol
Our Approach:
Flows
Objects
Aggregation
Batching
Recursion
input flow
output flow
aggregation
input flow
output flow
aggregation
output event
input flow
output flow
output event
input events
example: leader election protocol
3
3
9
6
aggregation
with “min”
example: leader election protocol
aggregation
with “min”
3
9
6
3
example: leader election protocol
aggregation
with “min”
3
9
6
3
example: leader election protocol
aggregation
with “min”
3
9
6
3
Different flavors of aggregation:
1.
In-order,
2.
Guarded,
3.
Coordinated,
4.
Etc.
formal,
abstract
properties
can reason
about global
behavior
Separation of Concerns
Separation of Concerns
We don’t specify:
1.
How values are aggregated
(in the network, in a centralized fashion)
2.
Which nodes interact with one-another
3.
What protocol is used
(token ring, scalable tree, gossip)
4.
Where the aggregated values emerge
5.
When and how often aggregation occurs
Separation of Concerns
We don’t specify:
1.
How values are aggregated
(in the network, in a centralized fashion)
2.
Which nodes interact with one-another
3.
What protocol is used
(token ring, scalable tree, gossip)
4.
Where the aggregated values emerge
5.
When and how often aggregation occurs
Separation of Concerns
We don’t specify:
1.
How values are aggregated
(in the network, in a centralized fashion)
2.
Which nodes interact with one-another
3.
What protocol is used
(token ring, scalable tree, gossip)
4.
Where the aggregated values emerge
5.
When and how often aggregation occurs
Separation of Concerns
We don’t specify:
1.
How values are aggregated
(in the network, in a centralized fashion)
2.
Which nodes interact with one-another
3.
What protocol is used
(token ring, scalable tree, gossip)
4.
Where the aggregated values emerge
5.
When and how often aggregation occurs
Separation of Concerns
We don’t specify:
1.
How values are aggregated
(in the network, in a centralized fashion)
2.
Which nodes interact with one-another
3.
What protocol is used
(token ring, scalable tree, gossip)
4.
Where the aggregated values emerge
5.
When and how often aggregation occurs
Separation of Concerns
We don’t specify:
1.
How values are aggregated
(in the network, in a centralized fashion)
2.
Which nodes interact with one-another
3.
What protocol is used
(token ring, scalable tree, gossip)
4.
Where the aggregated values emerge
5.
When and how often aggregation occurs
Aggregation with a Token Ring
Aggregation with a Token Ring
{1..3,5..6}{2..4, 6}{1..6}Aggregation with a Token Ring
{1..3,5..6}{2..4, 6}{1..6}token
leader node
Aggregation with a Token Ring
{1..3,5..6}{2..4, 6}{1..6}token
Aggregation with a Token Ring
{2..4, 6}{1..6}Aggregation with a Token Ring
{2..4, 6}{1..6}Aggregation with a Token Ring
{1..3,5..6}{2..4, 6}{1..6}
intersect
Aggregation with a Token Ring
{1..6}Aggregation with a Token Ring
{1..6}Aggregation with a Token Ring
{2..3, 6}{1..6}
intersect
Aggregation with a Token Ring
{2..3, 6}Our Approach:
Flows
Objects
Aggregation
Batching
Recursion
Batched Processing with Sets
node x
node y
node z
Batched Processing with Sets
node x
node y
node z
Batched Processing with Sets
node x
node y
node z
Batched Processing with Sets
node x
node y
node z
1
2
3
4
5
6
1
2
3
4
5
6
1
2
3
4
5
6
7
7
7
Batched Processing with Sets
node x
node y
node z
1
2
3
5
6
4
7
2
3
6
4
1
5
7
1
2
3
4
5
6
7
DROPPED:
Batched Processing with Sets
node x
node y
node z
1
2
3
5
6
2
3
6
4
1
2
3
4
5
6
Batched Processing with Sets
node x
node y
node z
1
2
3
5
6
2
3
6
4
1
2
3
4
5
6
Batched Processing with Sets
node x
node y
node z
1
2
3
5
6
2
3
6
4
1
2
3
4
5
6
Rec({1..3,5..6})Batched Processing with Sets
node x
node y
node z
1
2
3
5
6
2
3
6
4
1
2
3
4
5
6
Rec({1..3,5..6})Rec({2..4, 6})Batched Processing with Sets
node x
node y
node z
1
2
3
5
6
2
3
6
4
1
2
3
4
5
6
Rec({1..3,5..6})Rec({2..4, 6})Rec({1.. 6})Batched Processing with Sets
node x
node y
node z
1
2
3
5
6
2
3
6
4
1
2
3
4
5
6
example: which packets are stable?
{2..3,6}{1..3,5..6}
{1..6}aggregation
with “
”
{2..4,6}example: which packets are stable?
{2..3,6}{1..3,5..6}
{1..6}aggregation
with “
”
{2..4,6}example: which packets are stable?
{2..3,6}{1..3,5..6}
{1..6}aggregation
with “
”
{2..4,6}example: which packets are stable?
{2..3,6}{1..3,5..6}
{1..6}aggregation
with “
”
{2..4,6}Our Approach:
Flows
Objects
Aggregation
Batching
Recursion
Examples
01:
object
lock
(
bool
wants
)
:
bool
holds
02:
{03:
same
int
owner
;
04:
where
(
wants
)
05:
owner
:=
elect
(
id
);
06:
holds
:=
wants
(
owner
=
id
);
07:
}
embedding
distributed locking protocol
01:
object
elect
(
up
int
candidate
)
02:
:
s-up
int
leader
03:
{04:
s-up int
elected
:=
0
;
05:
where
(
fresh
elected
06:
elected
≤
candidate
)
07:
elected
:=
min
candidate
;
08:
leader
:=
elected
;
09:
}
leader election protocol
the core part
Conclusions
1.
Collaboration requires custom protocols
a)
Fine-tuned for a particular application semantics
b)
Fine-tuned for different networks and workloads
2.
Existing protocol languages don’t suffice
a)
Developers need a clean separation of concerns
3.
Modeling protocols as distributed flows
a)
Captures high-level protocol semantics concisely
b)
Reduces a coding burden on protocol developers
c)
Supports reasoning about the protocol behavior
d)
Provides a high degree of architectural flexibility
Conclusions
Thanks
"Exploring a Distributed Data Flow Language designed for Multi-Party Protocols, the research by Krzysztof Ostrowski, Ken Birman, and Danny Dolev from Cornell University and Hebrew University showcases innovative solutions for efficient data processing across distributed systems. The work highlights the importance of seamless communication and coordination in complex network environments."
Uploaded on Oct 10, 2024 | 0 Views
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Distributed Data Flow Language for Multi-Party Protocols Krzysztof Ostrowski , Ken Birman , Danny Dolev Cornell University, Hebrew University {krzys|ken}@cs.cornell.edu, dolev@cs.huji.ac.il
http://liveobjects.cs.cornell.edu node1 node2 user distributed peer-to-peer protocols node3
http://liveobjects.cs.cornell.edu node1 node2 user distributed peer-to-peer protocols multicast commit locking node3 replication
http://liveobjects.cs.cornell.edu user shared content distributed peer-to-peer protocols multicast commit locking replication
http://liveobjects.cs.cornell.edu user replicated content distributed peer-to-peer protocols multicast commit locking replication
http://liveobjects.cs.cornell.edu synchronization, coordination user replicated content distributed peer-to-peer protocols multicast commit locking replication
http://liveobjects.cs.cornell.edu node1 node2 user A2 A1 app. component A3 node3
http://liveobjects.cs.cornell.edu instance of the protocol stack Distributed Protocol Instance A2 P2 A1 app. P1 component P3 A3 instance of the protocol stack instance of the protocol stack
http://liveobjects.cs.cornell.edu instance of the protocol stack Distributed Protocol Instance A2 P2 A1 app. P1 component P3 events A3 instance of the protocol stack instance of the protocol stack
http://liveobjects.cs.cornell.edu instance of the protocol stack Distributed Protocol Instance A2 P2 m m network messages m m A1 app. P1 component P3 m events A3 instance of the protocol stack instance of the protocol stack
http://liveobjects.cs.cornell.edu proxy of the object Live Distributed Object (LO) basic building block P2 m m network messages m m P1 P3 m proxy of the object proxy of the object
http://liveobjects.cs.cornell.edu proxy of the object Live Distributed Object (LO) basic building block P2 m m network messages m m P1 P3 m proxy of the object proxy of the object
http://liveobjects.cs.cornell.edu proxy of the object Live Distributed Object (LO) basic building block P2 m m network messages m m P1 P3 m proxy of the object proxy of the object
http://liveobjects.cs.cornell.edu P2 m m P2 m P1 m P3 m m m m P2 P1 m P3 m m m m P2 P1 P3 m m m m m P2 P2 P1 m m m P3 m m m m m need lots of different objects (protocols) P1 P3 m m P1 P3 m m P2 P2 m m m m P1 m P3 m m m P1 P3 m m
http://liveobjects.cs.cornell.edu user-defined objects P2 m m P2 m P1 m P3 m m m m P2 P1 m P3 m m m m P2 P1 P3 m m m m m P2 P2 P1 m m m P3 m m m m m need lots of different objects (protocols) P1 P3 m m P1 P3 m m P2 P2 m m m m P1 m P3 m m m P1 P3 m m
How to Implement New Objects? custom user-defined object P2 m m m P1 P3 m m
How to Implement New Objects? Java / C# / C++ custom user-defined object protocol composition Frameworks (Ensemble, BAST, Appia) P2 m m m P1 P3 m m MACE, P2, etc.
How to Implement New Objects? Java / C# / C++ custom user-defined object protocol composition Frameworks (Ensemble, BAST, Appia) P2 m m m P1 P3 m m MACE, P2, etc.
How to Implement New Objects? Java / C# / C++ custom user-defined object protocol composition Frameworks (Ensemble, BAST, Appia) P2 m m m P1 P3 m m MACE, P2, etc.
How to Implement New Objects? higher-level logic (making decisions) Java / C# / C++ protocol composition Frameworks (Ensemble, BAST, Appia) intermingled, tightly-coupled lower-level logic (e.g., ACKs, timeouts, building rings/trees, internal bookkeeping) MACE, P2, etc.
How to Implement New Objects? higher-level logic (making decisions) intermingled, tightly-coupled lower-level logic (e.g., ACKs, timeouts, building rings/trees, internal bookkeeping)
How to Implement New Objects? higher-level logic (making decisions) intermingled, tightly-coupled Protocol 1 Protocol 2 node ACK/NAK recovery lower-level logic (e.g., ACKs, timeouts, building rings/trees, internal bookkeeping) Node node node Protocol 3 Region A A C AC node node node ABC AB BC C B B
How to Implement New Objects? harder to write/debug Java / C# / C++ error- prone protocol composition Frameworks (Ensemble, BAST, Appia) Protocol 1 Protocol 2 node ACK/NAK recovery Node node node Protocol 3 Region A A C AC node node node ABC AB BC C B less B sophisticated less MACE, P2, etc. flexibility
How to Implement New Objects? harder to write/debug Java / C# / C++ error- prone protocol composition Frameworks (Ensemble, BAST, Appia) Protocol 1 Protocol 2 node ACK/NAK recovery Node node node Protocol 3 Region A A C AC node node node ABC AB BC C B less B sophisticated less MACE, P2, etc. flexibility
How to Implement New Objects? harder to write/debug Java / C# / C++ error- prone protocol composition Frameworks (Ensemble, BAST, Appia) Protocol 1 Protocol 2 node ACK/NAK recovery Node node node Protocol 3 Region A A C AC node node node ABC AB BC C B less B sophisticated less MACE, P2, etc. flexibility
How to Implement New Objects? harder to write/debug Java / C# / C++ error- prone protocol composition Frameworks (Ensemble, BAST, Appia) Protocol 1 Protocol 2 node ACK/NAK recovery Node node node Protocol 3 Region A A C AC node node node ABC AB BC C B less B sophisticated less MACE, P2, etc. flexibility
How to Implement New Objects? separation of concerns higher-level logic (making decisions) Protocol 1 Protocol 2 node ACK/NAK recovery lower-level logic (e.g., ACKs, timeouts, building rings/trees, internal bookkeeping) Node node node Protocol 3 Region A A C AC node node node ABC AB BC C B B
How to Implement New Objects? separation of concerns programmer Protocol 1 Protocol 2 node ACK/NAK recovery Node compiler and runtime node node Protocol 3 Region A A C AC node node node ABC AB BC C B B
How to Implement New Objects? separation of concerns programmer Protocol 1 Protocol 2 node ACK/NAK recovery Node compiler and runtime node node Protocol 3 Region A A C AC node node node ABC AB BC C B B
Our Approach: Flows Objects Aggregation Batching Recursion
physical machine (node)
physical machine (node) node x1
software physical machine (node) node x1
layer 1 functional layer software node x1
layer 1 functional layers layer 2 software node x1
layer 1 functional layers interface exposed by layer2 layer 2 node x1
consumed by layer1 layer 1 functional layers interface exposed by layer2 layer 2 node x1
consumed by layer1 method call (event) layer 1 e1 interface exposed by layer2 layer 2 node x1
method call (event) layer 1 e1 occurred at time t0 layer 2 node x1
layer 1 e1 occurred at time t0 at node x1 layer 2 node x1
time layer 1 e1 later occurred at time t0 at node x1 layer 2 time is increasing bottom-up earlier t0 e1 node x1 x1 location (node)
time layer 1 e1 later occurred at time t0 at node x1 layer 2 time is increasing bottom-up earlier t0 e1 node x1 x1 location (node)
time layer 1 e1 later occurred at time t0 at node x1 layer 2 time is increasing bottom-up earlier t0 e1 node x1 x1 location (node)
time layer 1 e1 later layer 2 time is increasing bottom-up earlier t0 e1 node x1 x1 location (node)
time layer 1 layer 1 e2 later layer 2 layer 2 time is increasing bottom-up earlier e2 t1 t0 e1 node x1 node x2 x1 x2 x3 location (node)
time layer 1 layer 1 layer 1 e3 later layer 2 layer 2 layer 2 time is increasing bottom-up e3 t2 earlier e2 t1 t0 e1 node x1 node x2 node x3 x1 x2 x3 location (node)
time layer 1 layer 1 layer 1 e5 e4 later layer 2 layer 2 layer 2 time is increasing bottom-up e4 e5 t3 e3 t2 earlier e2 t1 t0 e1 node x1 node x2 node x3 x1 x2 x3 location (node)
time layer 1 layer 1 layer 1 e6 layer 2 layer 2 layer 2 e6 t4 e4 e5 t3 e3 t2 e2 t1 t0 e1 node x1 node x2 node x3 x1 x2 x3 location (node)
