Dynamic Computations in Ever-Changing Networks
Dynamic Computations
in Ever-Changing Networks
Idit Keidar
Technion, Israel
1
Idit Keidar, TADDS Sep 2011
TADDS: Theory of Dynamic
Distributed Systems
(This Workshop)
?
2
Idit Keidar, TADDS Sep 2011
What I Mean By “Dynamic”*
•
A
A
dynamic
dynamic
computation
computation
–
Continuously adapts its output
Continuously adapts its output
to reflect input and environment changes
to reflect input and environment changes
•
Other names
Other names
–
Live, on-going, continuous, stabilizing
Live, on-going, continuous, stabilizing
*In this talk
3
Idit Keidar, TADDS Sep 2011
In This Talk: Three Examples
•
Continuous (dynamic) weighted matching
•
Live monitoring
–
(Dynamic) average aggregation)
•
Peer sampling
–
Aka gossip-based membership
4
Idit Keidar, TADDS Sep 2011
Ever-Changing Networks*
•
Where dynamic computations are interesting
•
Network (nodes, links) constantly changes
•
Computation inputs constantly change
–
E.g., sensor reads
•
Examples:
–
Ad-hoc, vehicular nets – mobility
–
Sensor nets – battery, weather
–
Social nets – people change friends, interests
–
Clouds spanning multiple data-centers – churn
*My name for “dynamic” networks
5
Idit Keidar, TADDS Sep 2011
Continuous Weighted
Matching
in Dynamic Networks
With Liat Atsmon Guz, Gil Zussman
Dynamic
Ever-Changing
6
Idit Keidar, TADDS Sep 2011
Weighted Matching
•
Motivation: schedule transmissions in
wireless network
•
Links have weights,
w:E→ℝ
–
Can represent message queue lengths,
throughput, etc.
•
Goal: maximize matching weight
•
M
opt
– a matching with maximum weight
8
5
2
9
4
10
3
1
w(M
opt
)=17
7
Idit Keidar, TADDS Sep 2011
Model
•
Network is ever-changing, or
Network is ever-changing, or
dynamic
dynamic
–
Also called time-varying graph, dynamic
Also called time-varying graph, dynamic
communication network, evolving graph
communication network, evolving graph
–
E
E
t
t
,
,
V
V
t
t
are time-varying sets,
are time-varying sets,
w
w
t
t
is a time-
is a time-
varying function
varying function
•
Asynchronous communication
Asynchronous communication
•
No message loss unless links/node crash
No message loss unless links/node crash
–
Perfect failure detection
Perfect failure detection
Idit Keidar, TADDS Sep 2011
8
Continuous Matching Problem
1.
At any time t, every node v
At any time t, every node v
∈
∈
V
V
t
t
outputs
outputs
either
either
⊥
⊥
or a neighbor u
or a neighbor u
∈
∈
V
V
t
t
as its match
as its match
2.
If the network eventually stops changing,
If the network eventually stops changing,
then eventually, every node v outputs u
then eventually, every node v outputs u
iff u outputs v
iff u outputs v
•
Defining the
Defining the
matching at time t
matching at time t
:
:
–
A link e=(u,v)
A link e=(u,v)
∈
∈
M
M
t
t
, if both u and v output
, if both u and v output
each other as their match at time t
each other as their match at time t
–
Note
Note
: matching defined pre-convergence
: matching defined pre-convergence
Idit Keidar, TADDS Sep 2011
9
Classical Approach to Matching
•
One-shot (static) algorithms
One-shot (static) algorithms
•
Run periodically
Run periodically
–
Each time over static input
Each time over static input
•
Bound
Bound
convergence time
convergence time
–
Best known in asynchronous networks is
Best known in asynchronous networks is
O(|V|)
O(|V|)
•
Bound
Bound
approximation ratio
approximation ratio
at the end
at the end
–
Typically
Typically
2
2
•
Don’t use the matching while algorithm is
Don’t use the matching while algorithm is
running
running
–
“Control phase”
“Control phase”
Idit Keidar, TADDS Sep 2011
10
Self-Stabilizing Approach
•
[Manne et al. 2008]
•
Run all the time
–
Adapt to changes
•
But, even a small change can destabilize
the entire matching for a long time
•
Still same metrics:
–
Convergence time from arbitrary state
–
Approximation after convergence
Idit Keidar, TADDS Sep 2011
11
Our Approach: Maximize
Matching “All the Time”
•
Run constantly
–
Like self-stabilizing
•
Do not wait for convergence
–
It might never happen in a dynamic network!
•
Strive for stability
–
Keep current matching edges in the matching as
much as possible
•
Bound approximation throughout the run
–
Local steps can take us back to the
approximation quickly after a local change
Idit Keidar, TADDS Sep 2011
12
Continuous Matching Strawman
•
Asynchronous matching using Hoepman’s
(1-shot) Algorithm
–
Always pick “locally” heaviest link for the
matching
–
Convergence in O(|V|) time from scratch
•
Use same rule dynamically: if new locally
heaviest link becomes available, grab it
and drop conflicting links
Idit Keidar, TADDS Sep 2011
13
Strawman Example 1
11
10
9
14
10
9
12
11
7
8
W(M
opt
)=45
W(M)=20
Can take
Ω
(|V|) time to
converge to
approximation!
2-approximation
reached
Idit Keidar, TADDS Sep 2011
Strawman Example 2
Idit Keidar, TADDS Sep 2011
15
9
7
6
8
10
9
W(M)=24
W(M)=16
W(M)=17
Can decrease the matching weight!
DynaMatch Algorithm Idea
•
Grab maximal augmenting links
Grab maximal augmenting links
–
A link e is
A link e is
augmenting
augmenting
if adding e to M
if adding e to M
increases w(M)
increases w(M)
–
Augmentation weight
Augmentation weight
w(e)-w(M
w(e)-w(M
∩
∩
adj(e)) > 0
adj(e)) > 0
–
A
A
maximal augmenting
maximal augmenting
link has maximum
link has maximum
augmentation weight among adjacent links
augmentation weight among adjacent links
Idit Keidar, TADDS Sep 2011
16
4
9
7
3
1
augmenting
but NOT maximal
maximal
augmenting
•
More stable after changes
•
Monotonically increasing matching weight
Example 2 Revisited
17
9
7
6
8
10
9
Idit Keidar, TADDS Sep 2011
Example 1 Revisited
•
Faster convergence to approximation
18
11
10
9
10
9
12
11
7
8
11
10
9
10
9
12
11
7
8
Idit Keidar, TADDS Sep 2011
General Result
•
After a local change
–
Link/node added, removed, weight change
•
Convergence to approximation within
constant number of steps
–
Even before algorithm is quiescent (stable)
–
Assuming it has stabilized before the change
Idit Keidar, TADDS Sep 2011
19
LiMoSense – Live Monitoring in
Dynamic Sensor Networks
With Ittay Eyal, Raphi Rom
ALGOSENSORS'11
Dynamic
Ever-Changing
20
Idit Keidar, TADDS Sep 2011
The Problem
•
In sensor network
In sensor network
–
Each sensor has a read value
Each sensor has a read value
•
Average aggregation
Average aggregation
–
Compute average of read values
Compute average of read values
•
Live monitoring
Live monitoring
–
Inputs constantly change
Inputs constantly change
–
Dynamically compute “current” average
Dynamically compute “current” average
•
Motivation
Motivation
–
Environmental monitoring
Environmental monitoring
–
Cloud facility load monitoring
Cloud facility load monitoring
Idit Keidar, TADDS Sep 2011
21
7
12
8
23
5
5
10
11
22
Requirements
•
Robustness
Robustness
–
Message loss
Message loss
–
Link failure/recovery – battery decay, weather
Link failure/recovery – battery decay, weather
–
Node crash
Node crash
•
Limited bandwidth (battery), memory in
Limited bandwidth (battery), memory in
nodes (motes)
nodes (motes)
•
No centralized server
No centralized server
–
Challenge: cannot collect the values
Challenge: cannot collect the values
–
Employ
Employ
in-network
in-network
aggregation
aggregation
Idit Keidar, TADDS Sep 2011
22
Previous Work: One-Shot
Average Aggregation
•
Assumes static input (sensor reads)
Assumes static input (sensor reads)
•
Output at all nodes
Output at all nodes
converges
converges
to average
to average
•
Gossip-based solution [Kempe et al.]
Gossip-based solution [Kempe et al.]
–
Each node holds weighted estimate
Each node holds weighted estimate
–
Sends part of its weight to a neighbor
Sends part of its weight to a neighbor
Idit Keidar, TADDS Sep 2011
23
10,1
7,1
10,0.5
10,0.5
8,1.5
8.5, ..
8.5, ..
Invariant
: read sum =
weighted sum at all nodes and links
LiMoSense: Live Aggregation
•
Adjust to read value changes
•
Challenge: old read value may have
spread to an unknown set of nodes
•
Idea: update weighted estimate
–
To fix the invariant
•
Adjust the estimate:
Idit Keidar, TADDS Sep 2011
24
Adjusting The Estimate
Idit Keidar, TADDS Sep 2011
25
Case 1:
Case 2:
Example: read value 0
1
Before
After
3,1
3,2
3.5,2
4,1
Robust Aggregation Challenges
•
Message loss
–
Breaks the invariant
–
Solution idea: send summary of all previous
values transmitted on the link
•
Weight
infinity
–
Solution idea: hybrid push-pull solution, pull
with negative weights
•
Link/node failures
–
Solution idea: undo sent messages
Idit Keidar, TADDS Sep 2011
26
Correctness Results
•
Theorem 1
: The invariant always holds
•
Theorem 2
: After GST, all estimates
converge to the average
•
Convergence rate: exponential decay of
mean square error
Idit Keidar, TADDS Sep 2011
27
Simulation Example
•
100 nodes
•
Input: standard
normal distribution
•
10 nodes change
–
Values +10
Idit Keidar, TADDS Sep 2011
28
Simulation Example 2
•
100 nodes
•
Input: standard
normal distribution
•
Every 10 steps,
–
10 nodes change
values +0.01
Idit Keidar, TADDS Sep 2011
29
Summary
•
LiMoSense – Live Average Monitoring
–
Aggregate dynamic data reads
•
Fault tolerant
–
Message loss, link failure, node crash
•
Correctness in dynamic asynchronous
settings
•
Exponential convergence after GST
•
Quick reaction to dynamic behavior
Idit Keidar, TADDS Sep 2011
30
Correctness of Gossip-Based
Membership under Message Loss
With Maxim Gurevich
PODC'09; SICOMP 2010
Dynamic
31
Idit Keidar, TADDS Sep 2011
The Setting
•
Many nodes –
n
–
10,000s, 100,000s, 1,000,000s, …
•
Come and go
–
Churn (=ever-changing input)
•
Fully connected network topology
–
Like the Internet
•
Every joining node knows some others
–
(Initial) Connectivity
32
Idit Keidar, TADDS Sep 2011
Membership or Peer Sampling
•
Each node needs to know some live nodes
Each node needs to know some live nodes
•
Has a
Has a
view
view
–
Set of node ids
Set of node ids
–
Supplied to the application
Supplied to the application
–
Constantly refreshed (= dynamic output)
Constantly refreshed (= dynamic output)
•
Typical size –
Typical size –
log n
log n
33
Idit Keidar, TADDS Sep 2011
Applications
•
Applications
Applications
–
Gossip-based algorithm
Gossip-based algorithm
–
Unstructured overlay networks
Unstructured overlay networks
–
Gathering statistics
Gathering statistics
•
Work best with
Work best with
random node samples
random node samples
–
Gossip algorithms converge fast
Gossip algorithms converge fast
–
Overlay networks are robust, good expanders
Overlay networks are robust, good expanders
–
Statistics are accurate
Statistics are accurate
34
Idit Keidar, TADDS Sep 2011
Modeling Membership Views
•
Modeled as a directed graph
u
v
w
y
35
Idit Keidar, TADDS Sep 2011
Modeling Protocols: Graph
Transformations
•
View is used for maintenance
•
Example: push protocol
u
v
w
z
36
Idit Keidar, TADDS Sep 2011
Desirable Properties?
•
Randomness
Randomness
–
View should include random samples
View should include random samples
•
Holy grail for samples: IID
Holy grail for samples: IID
–
Each sample
Each sample
uniformly
uniformly
distributed
distributed
–
Each sample
Each sample
independent
independent
of other samples
of other samples
•
Avoid spatial dependencies among view entries
Avoid spatial dependencies among view entries
•
Avoid correlations between nodes
Avoid correlations between nodes
–
Good
Good
load balance
load balance
among nodes
among nodes
37
Idit Keidar, TADDS Sep 2011
What About Churn?
•
Views should constantly evolve
Views should constantly evolve
–
Remove failed nodes, add joining ones
Remove failed nodes, add joining ones
•
Views should evolve to IID from
Views should evolve to IID from
any
any
state
state
•
Minimize
Minimize
temporal dependencies
temporal dependencies
–
Dependence on the past should decay quickly
Dependence on the past should decay quickly
–
Useful for application requiring fresh samples
Useful for application requiring fresh samples
38
Idit Keidar, TADDS Sep 2011
Global Markov Chain
•
A
A
global state
global state
– all
– all
n
n
views in the system
views in the system
•
A protocol action – transition between global
A protocol action – transition between global
states
states
•
Global Markov Chain
Global Markov Chain
G
G
u
v
u
v
39
Idit Keidar, TADDS Sep 2011
Defining Properties Formally
•
Small views
–
Bounded
dout(u)
•
Load balance
–
Low variance of
din(u)
•
From any starting state, eventually
(In the stationary distribution of MC on G)
–
Uniformity
•
Pr(v
u.view) =
Pr(w
u.view)
–
Spatial independence
•
Pr(v
u. view| y
w. view) =
Pr(v
u. view)
–
Perfect uniformity + spatial independence
load
balance
40
Idit Keidar, TADDS Sep 2011
Temporal Independence
•
Time to obtain views independent of the
past
•
From an
expected
state
–
Refresh rate in the steady state
•
Would have been much longer had we
considered starting from
arbitrary state
–
O(n
14
)
[Cooper09]
41
Idit Keidar, TADDS Sep 2011
Existing Work: Practical
Protocols
•
Tolerates asynchrony, message loss
Tolerates asynchrony, message loss
•
Studied only empirically
Studied only empirically
–
Good load balance
Good load balance
[Lpbcast, Jelasity et al 07]
[Lpbcast, Jelasity et al 07]
–
Fast decay of temporal dependencies
Fast decay of temporal dependencies
[Jelasity et al 07]
[Jelasity et al 07]
–
Induce spatial dependence
Induce spatial dependence
Push protocol
u
v
w
u
v
w
z
z
42
Idit Keidar, TADDS Sep 2011
Existing Work: Analysis
•
Analyzed theoretically
Analyzed theoretically
[Allavena et al 05, Mahlmann et al 06]
[Allavena et al 05, Mahlmann et al 06]
–
Uniformity, load balance, spatial independence
Uniformity, load balance, spatial independence
–
Weak bounds (worst case) on temporal independence
Weak bounds (worst case) on temporal independence
•
Unrealistic assumptions – hard to implement
Unrealistic assumptions – hard to implement
–
Atomic actions with bi-directional communication
Atomic actions with bi-directional communication
–
No message loss
No message loss
u
v
w
z
Shuffle protocol
*
43
Idit Keidar, TADDS Sep 2011
Our Contribution :
Bridge This Gap
•
A
A
practical
practical
protocol
protocol
–
Tolerates message loss, churn, failures
Tolerates message loss, churn, failures
–
No complex bookkeeping for atomic actions
No complex bookkeeping for atomic actions
•
Formally
Formally
prove the desirable properties
prove the desirable properties
–
Including under message loss
Including under message loss
44
Idit Keidar, TADDS Sep 2011
Send & Forget Membership
•
The best of push and shuffle
u
v
w
45
•
Perfect
Perfect
randomness without loss
randomness without loss
Idit Keidar, TADDS Sep 2011
S&F: Message Loss
•
Message loss
–
Or no empty entries in v’s view
u
v
w
u
v
w
46
Idit Keidar, TADDS Sep 2011
S&F: Compensating for Loss
•
Edges (view entries) disappear due to loss
•
Need to prevent views from emptying out
•
Keep the sent ids when too few ids in view
–
Push-like when views are too small
–
But rare enough to limit dependencies
u
v
w
u
v
w
47
Idit Keidar, TADDS Sep 2011
S&F: Advantages
•
No bi-directional communication
–
No complex bookkeeping
–
Tolerates message loss
•
Simple
–
Without unrealistic assumptions
–
Amenable to formal analysis
Easy to
implement
48
Idit Keidar, TADDS Sep 2011
•
Degree distribution (load balance)
•
Stationary distribution of MC on global
graph G
–
Uniformity
–
Spatial Independence
–
Temporal Independence
•
Hold even under (reasonable) message
loss!
Key Contribution: Analysis
49
Idit Keidar, TADDS Sep 2011
Conclusions
•
Ever-changing networks
Ever-changing networks
are here to stay
are here to stay
•
In these, need to solve
In these, need to solve
dynamic
dynamic
versions
versions
of network problems
of network problems
•
We discussed three examples
We discussed three examples
–
Matching
Matching
–
Monitoring
Monitoring
–
Peer sampling
Peer sampling
•
Many more have yet to be studied
Many more have yet to be studied
50
Idit Keidar, TADDS Sep 2011
Thanks!
•
Liat Atsmon Guz, Gil Zussman
•
Ittay Eyal, Raphi Rom
•
Maxim Gurevich
Idit Keidar, TADDS Sep 2011
51
Dynamic computations in ever-changing networks involve continuously adapting output to reflect input and environmental changes. This talk by Idit Keidar at TADDS Sep. 2011 explores the concept further, presenting examples like continuous weighted matching, live monitoring, and peer sampling. The discussion covers the challenges and dynamics of networks where computations are constantly interesting due to nodes and links changing, along with input variations such as sensor readings. Keidar delves into the specifics of dynamic continuous weighted matching in dynamic networks, emphasizing the motivation behind it and the evolving nature of network models.
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
Dynamic Computations in Ever-Changing Networks Idit Keidar Technion, Israel Idit Keidar, TADDS Sep 2011 1
? TADDS: Theory of Dynamic Distributed Systems (This Workshop) Idit Keidar, TADDS Sep 2011 2
What I Mean By Dynamic* A dynamic computation Continuously adapts its output to reflect input and environment changes Other names Live, on-going, continuous, stabilizing *In this talk Idit Keidar, TADDS Sep 2011 3
In This Talk: Three Examples Continuous (dynamic) weighted matching Live monitoring (Dynamic) average aggregation) Peer sampling Aka gossip-based membership Idit Keidar, TADDS Sep 2011 4
Ever-Changing Networks* Where dynamic computations are interesting Network (nodes, links) constantly changes Computation inputs constantly change E.g., sensor reads Examples: Ad-hoc, vehicular nets mobility Sensor nets battery, weather Social nets people change friends, interests Clouds spanning multiple data-centers churn *My name for dynamic networks Idit Keidar, TADDS Sep 2011 5
Dynamic Continuous Weighted Matching in Dynamic Networks Ever-Changing With Liat Atsmon Guz, Gil Zussman Idit Keidar, TADDS Sep 2011 6
Weighted Matching Motivation: schedule transmissions in wireless network Links have weights, w:E Can represent message queue lengths, throughput, etc. Goal: maximize matching weight Mopt a matching with maximum weight 5 4 8 w(Mopt)=17 10 2 3 9 1 7 Idit Keidar, TADDS Sep 2011
Model Network is ever-changing, or dynamic Also called time-varying graph, dynamic communication network, evolving graph Et,Vt are time-varying sets, wt is a time- varying function Asynchronous communication No message loss unless links/node crash Perfect failure detection Idit Keidar, TADDS Sep 2011 8
Continuous Matching Problem 1. At any time t, every node v Vt outputs either or a neighbor u Vt as its match 2. If the network eventually stops changing, then eventually, every node v outputs u iff u outputs v Defining the matching at time t: A link e=(u,v) Mt, if both u and v output each other as their match at time t Note: matching defined pre-convergence Idit Keidar, TADDS Sep 2011 9
Classical Approach to Matching One-shot (static) algorithms Run periodically Each time over static input Bound convergence time Best known in asynchronous networks is O(|V|) Bound approximation ratio at the end Typically 2 Don t use the matching while algorithm is running Control phase Idit Keidar, TADDS Sep 2011 10
Self-Stabilizing Approach [Manne et al. 2008] Run all the time Adapt to changes But, even a small change can destabilize the entire matching for a long time Still same metrics: Convergence time from arbitrary state Approximation after convergence Idit Keidar, TADDS Sep 2011 11
Our Approach: Maximize Matching All the Time Run constantly Like self-stabilizing Do not wait for convergence It might never happen in a dynamic network! Strive for stability Keep current matching edges in the matching as much as possible Bound approximation throughout the run Local steps can take us back to the approximation quickly after a local change Idit Keidar, TADDS Sep 2011 12
Continuous Matching Strawman Asynchronous matching using Hoepman s (1-shot) Algorithm Always pick locally heaviest link for the matching Convergence in O(|V|) time from scratch Use same rule dynamically: if new locally heaviest link becomes available, grab it and drop conflicting links Idit Keidar, TADDS Sep 2011 13
Strawman Example 1 12 11 10 9 W(Mopt)=45 W(M)=20 11 10 9 8 7 Can take (|V|) time to converge to approximation! 12 11 10 9 11 10 9 8 7 W(M)=21 12 11 10 9 11 10 9 8 7 W(M)=22 2-approximation reached 12 11 10 9 11 10 9 8 7 W(M)=29 14 Idit Keidar, TADDS Sep 2011
Strawman Example 2 10 9 8 9 7 6 W(M)=24 10 9 8 9 7 6 W(M)=16 10 9 8 9 7 6 W(M)=17 Can decrease the matching weight! Idit Keidar, TADDS Sep 2011 15
DynaMatch Algorithm Idea Grab maximal augmenting links A link e is augmenting if adding e to M increases w(M) Augmentation weight w(e)-w(M adj(e)) > 0 A maximal augmenting link has maximum augmentation weight among adjacent links augmenting but NOT maximal 9 maximal augmenting 3 4 1 7 Idit Keidar, TADDS Sep 2011 16
Example 2 Revisited More stable after changes Monotonically increasing matching weight 10 9 8 9 7 6 Idit Keidar, TADDS Sep 2011 17
Example 1 Revisited Faster convergence to approximation 12 11 10 9 11 10 9 8 7 12 11 10 9 11 10 9 8 7 Idit Keidar, TADDS Sep 2011 18
General Result After a local change Link/node added, removed, weight change Convergence to approximation within constant number of steps Even before algorithm is quiescent (stable) Assuming it has stabilized before the change Idit Keidar, TADDS Sep 2011 19
Dynamic LiMoSense Live Monitoring in Dynamic Sensor Networks Ever-Changing With Ittay Eyal, Raphi Rom ALGOSENSORS'11 Idit Keidar, TADDS Sep 2011 20
The Problem 7 5 In sensor network Each sensor has a read value Average aggregation Compute average of read values Live monitoring Inputs constantly change Dynamically compute current average Motivation Environmental monitoring Cloud facility load monitoring 12 10 11 8 22 23 5 Idit Keidar, TADDS Sep 2011 21
Requirements Robustness Message loss Link failure/recovery battery decay, weather Node crash Limited bandwidth (battery), memory in nodes (motes) No centralized server Challenge: cannot collect the values Employ in-network aggregation Idit Keidar, TADDS Sep 2011 22
Previous Work: One-Shot Average Aggregation Assumes static input (sensor reads) Output at all nodes converges to average Gossip-based solution [Kempe et al.] Each node holds weighted estimate Sends part of its weight to a neighbor t 8,1.5 10,0.5 8.5, .. 8.5, .. 10,1 10,0.5 7,1 Invariant: read sum = weighted sum at all nodes and links Idit Keidar, TADDS Sep 2011 23
LiMoSense: Live Aggregation Adjust to read value changes Challenge: old read value may have spread to an unknown set of nodes Idea: update weighted estimate To fix the invariant Adjust the estimate: ( newRead i i i w 1 ) + prevRead est est i i Idit Keidar, TADDS Sep 2011 24
Adjusting The Estimate 1 w ( ) + newRead prevRead est est i i i i i Example: read value 0 1 Before 3,1 After 4,1 Case 1: 3,2 3.5,2 Case 2: Idit Keidar, TADDS Sep 2011 25
Robust Aggregation Challenges Message loss Breaks the invariant Solution idea: send summary of all previous values transmitted on the link Weight infinity Solution idea: hybrid push-pull solution, pull with negative weights Link/node failures Solution idea: undo sent messages Idit Keidar, TADDS Sep 2011 26
Correctness Results Theorem 1: The invariant always holds Theorem 2: After GST, all estimates converge to the average Convergence rate: exponential decay of mean square error Idit Keidar, TADDS Sep 2011 27
Simulation Example 100 nodes Input: standard normal distribution 10 nodes change Values +10 Idit Keidar, TADDS Sep 2011 28
Simulation Example 2 100 nodes Input: standard normal distribution Every 10 steps, 10 nodes change values +0.01 Idit Keidar, TADDS Sep 2011 29
Summary LiMoSense Live Average Monitoring Aggregate dynamic data reads Fault tolerant Message loss, link failure, node crash Correctness in dynamic asynchronous settings Exponential convergence after GST Quick reaction to dynamic behavior Idit Keidar, TADDS Sep 2011 30
Dynamic Correctness of Gossip-Based Membership under Message Loss With Maxim Gurevich PODC'09; SICOMP 2010 Idit Keidar, TADDS Sep 2011 31
The Setting Many nodes n 10,000s, 100,000s, 1,000,000s, Come and go Churn (=ever-changing input) Fully connected network topology Like the Internet Every joining node knows some others (Initial) Connectivity Idit Keidar, TADDS Sep 2011 32
Membership or Peer Sampling Each node needs to know some live nodes Has a view Set of node ids Supplied to the application Constantly refreshed (= dynamic output) Typical size log n Idit Keidar, TADDS Sep 2011 33
Applications Applications Gossip-based algorithm Unstructured overlay networks Gathering statistics Work best with random node samples Gossip algorithms converge fast Overlay networks are robust, good expanders Statistics are accurate Idit Keidar, TADDS Sep 2011 34
Modeling Membership Views Modeled as a directed graph w y v y w u v Idit Keidar, TADDS Sep 2011 35
Modeling Protocols: Graph Transformations View is used for maintenance Example: push protocol w z w v w w z u v Idit Keidar, TADDS Sep 2011 36
Desirable Properties? Randomness View should include random samples Holy grail for samples: IID Each sample uniformly distributed Each sample independent of other samples Avoid spatial dependencies among view entries Avoid correlations between nodes Good load balance among nodes Idit Keidar, TADDS Sep 2011 37
What About Churn? Views should constantly evolve Remove failed nodes, add joining ones Views should evolve to IID from any state Minimize temporal dependencies Dependence on the past should decay quickly Useful for application requiring fresh samples Idit Keidar, TADDS Sep 2011 38
Global Markov Chain A global state all n views in the system A protocol action transition between global states Global Markov Chain G u v u v Idit Keidar, TADDS Sep 2011 39
Defining Properties Formally Small views Bounded dout(u) Load balance Low variance of din(u) From any starting state, eventually (In the stationary distribution of MC on G) Uniformity Pr(v u.view) = Pr(w u.view) Spatial independence Pr(v u. view| y w. view) = Pr(v u. view) Perfect uniformity + spatial independence load balance Idit Keidar, TADDS Sep 2011 40
Temporal Independence Time to obtain views independent of the past From an expected state Refresh rate in the steady state Would have been much longer had we considered starting from arbitrary state O(n14) [Cooper09] Idit Keidar, TADDS Sep 2011 41
Existing Work: Practical Protocols Push protocol w w z z v v u u w Tolerates asynchrony, message loss Studied only empirically Good load balance [Lpbcast, Jelasity et al 07] Fast decay of temporal dependencies [Jelasity et al 07] Induce spatial dependence Idit Keidar, TADDS Sep 2011 42
Existing Work: Analysis w z Shuffle protocol * z w v z v w u v z w Analyzed theoretically [Allavena et al 05, Mahlmann et al 06] Uniformity, load balance, spatial independence Weak bounds (worst case) on temporal independence Unrealistic assumptions hard to implement Atomic actions with bi-directional communication No message loss Idit Keidar, TADDS Sep 2011 43
Our Contribution : Bridge This Gap A practical protocol Tolerates message loss, churn, failures No complex bookkeeping for atomic actions Formally prove the desirable properties Including under message loss Idit Keidar, TADDS Sep 2011 44
Send & Forget Membership The best of push and shuffle w Some view entries may be empty u w u v u w v w Perfect randomness without loss Idit Keidar, TADDS Sep 2011 45
S&F: Message Loss Message loss Or no empty entries in v s view w w u v u v Idit Keidar, TADDS Sep 2011 46
S&F: Compensating for Loss Edges (view entries) disappear due to loss Need to prevent views from emptying out Keep the sent ids when too few ids in view Push-like when views are too small But rare enough to limit dependencies w w u v u v Idit Keidar, TADDS Sep 2011 47
S&F: Advantages No bi-directional communication No complex bookkeeping Tolerates message loss Simple Without unrealistic assumptions Amenable to formal analysis Easy to implement Idit Keidar, TADDS Sep 2011 48
Key Contribution: Analysis Degree distribution (load balance) Stationary distribution of MC on global graph G Uniformity Spatial Independence Temporal Independence Hold even under (reasonable) message loss! Idit Keidar, TADDS Sep 2011 49
Conclusions Ever-changing networks are here to stay In these, need to solve dynamic versions of network problems We discussed three examples Matching Monitoring Peer sampling Many more have yet to be studied Idit Keidar, TADDS Sep 2011 50
